Fibonacci words
and round numbers
Weekly challenge 150 — 31 January 2022
Week 150: 31 Jan 2022
Write a script to generate all square-free integers <= 500. In mathematics, a square-free integer is an integer which is divisible by no perfect square other than 1. That is, its prime factorisation has exactly one factor for each prime that appears in it. For example, 10 = 2 × 5 is square-free, but 18 = 2 × 3 × 3 is not, because 18 is divisible by 9 = 3**2.
The smallest positive square-free integers are 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, ...
This is going to be one of those tasks where someone will have a quick solution using number theory, someone else will tell us there's a Perl module to do it, and we'll probably see a few one-line answers as well.
Mine is none of these. I modified the method of my good friend Eratosthenes to say:
A little thought allows some optimisation of the striking out:
But the optimisation makes no discernable difference even if we extend the limit to a million.
#!/usr/bin/perl # Peter Campbell Smith - 2022-01-31 # PWC 150 task 2 use v5.28; use strict; use warnings; use utf8; my ($j, $mult, $no_good, $square, $top, @sfi, $results, $count); $top = 500; # let's start by guessing that all integers are square-free for $j (1 .. $top) { $sfi[$j] = 1; } # now let's knock out anything that is a multiple of a square for $j (2 .. int(sqrt($top))) { next unless $sfi[$j]; # no need to bother if $j is a known non-square-free $square = $j ** 2; for ($mult = 1;; $mult ++) { $no_good = $mult * $square; last if $no_good > $top; $sfi[$no_good] = 0; } } # output what's left neatly say qq[Square-free integers <= $top: ]; $count = 1; for $j (1 .. $top) { next unless $sfi[$j]; $results .= sprintf('%3d',$j) . ', '; $results .= qq[\n] unless ($count++ % 10); } $results =~ s|[, \n]+$||; say $results;
Square-free integers <= 500: 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113, 114, 115, 118, 119, 122, 123, 127, 129, 130, 131, 133, 134, 137, 138, 139, 141, 142, 143, 145, 146, 149, 151, 154, 155, 157, 158, 159, 161, 163, 165, 166, 167, 170, 173, 174, 177, 178, 179, 181, 182, 183, 185, 186, 187, 190, 191, 193, 194, 195, 197, 199, 201, 202, 203, 205, 206, 209, 210, 211, 213, 214, 215, 217, 218, 219, 221, 222, 223, 226, 227, 229, 230, 231, 233, 235, 237, 238, 239, 241, 246, 247, 249, 251, 253, 254, 255, 257, 258, 259, 262, 263, 265, 266, 267, 269, 271, 273, 274, 277, 278, 281, 282, 283, 285, 286, 287, 290, 291, 293, 295, 298, 299, 301, 302, 303, 305, 307, 309, 310, 311, 313, 314, 317, 318, 319, 321, 322, 323, 326, 327, 329, 330, 331, 334, 335, 337, 339, 341, 345, 346, 347, 349, 353, 354, 355, 357, 358, 359, 362, 365, 366, 367, 370, 371, 373, 374, 377, 379, 381, 382, 383, 385, 386, 389, 390, 391, 393, 394, 395, 397, 398, 399, 401, 402, 403, 406, 407, 409, 410, 411, 413, 415, 417, 418, 419, 421, 422, 426, 427, 429, 430, 431, 433, 434, 435, 437, 438, 439, 442, 443, 445, 446, 447, 449, 451, 453, 454, 455, 457, 458, 461, 462, 463, 465, 466, 467, 469, 470, 471, 473, 474, 478, 479, 481, 482, 483, 485, 487, 489, 491, 493, 494, 497, 498, 499
Any content of this website which has been created by Peter Campbell Smith is in the public domain