# No Squares Allowed

Wherein we establish some ground-rules for this clubhouse.

#### THE WEEKLY CHALLENGE – PERL & RAKU #150 TASK 2

no squares in my circle
— anon

### Square-free Integer

Write a script to generate all square-free integers <= 500.

In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no perfect square other than 1. That is, its prime factorization 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.

##### Example
``````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, ...``````

#### Method

We’re going to make stab at sidestepping a lot of complexity solving this one. We could, for instance, spend a lot of time compiling lists of all factors for each candidate value, and then somehow make sure none of those factors have an integral square root, which would mean the candidate contained a perfect square.

That, as they say, would be a long road to hoe. The scenic route, taking in all the sights and hardly paying attention to any of it. What a drag. Not hip at all.

Alternately we could go at it from the other direction: compile a list of just the proscribed values and use them as possible divisors on each candidate, until the test square is more than the candidate.

Which means we need a list of squares.

The number of perfect squares available less than (or equal to) the candidate is going to be much smaller than the candidate, or a list of all its possible factors. We don’t actually care much at all about its composite makeup, only whether or not those squares are in there. So we’ll focus just on them.

Now that, that sounds like a plan. We’ll do that instead.

The largest square we will need to consider is the size of the candidate itself. It’s a small list we’re compiling here and we can divide out each one to make sure the result doesn’t come out whole. The question remains, though, of when do we know when to stop looking further? I mean, on one level it’s not necessary: we could compile a list of squares up to the maximum value and use the whole list. For square-frees up to 500 that’s 21 values, one less than the whole part of the square root. Repeating those divisions 500 times makes for 11,000 calculations. This will not even wake the sleepy kittens. It will certainly not make them cry.

But I felt like thinking through some optimizations anyway. I wanted to avoid constantly having to check whether our test square is too large, using something like

``last if \$square > \$candidate;``

to know when we can safely stop.

It’s a simple check but repetitive; it needs to be made against every square, for every candidate. So what if the list of squares we were using were already the right size? Then we wouldn’t need to check.

The first idea, using a `grep` filter on the `@all_squares` list, proved to be unexpectedly expensive. This was even if we only use it once per iteration, to narrow the list and select only those squares less that the candidate to loop over. We ended up noticeably worse off for our efforts, remarkably taking about twice the time to finish.

Did not see that coming.

So instead I considered how all that filtering was in itself repetitive — and hence wasteful —as the list of squares starts small and only gets progressively larger as the candidate size increases. Once we put 4 into the list we never need to check it again; it will always be there. So why check to make sure it’s still a valid option when we know for a fact it will be?

The solution was to use two lists.

I created a master list of all squares we might need and a second, running list of valid squares for a candidate, which is kept up-to-date by moving values from one list over to the other. As each candidate is considered, its value is compared against the smallest remaining master element, and if it matches we do three things:

1. we remove the square from the master list
2. we update the working list with the new square and,
3. since we know that square is equal to the candidate, we fail the candidate and move on.

This shaved significant processing time, which would matter if we were to want say 500,000 values instead of 500. It wasn’t necessary for this specific problem at all but I liked the pattern of one list updating the other, so we are always checking only the squares in the range we need, without further needing to verify that range throughout the search.

##### PERL 5 SOLUTION

``````my \$max = shift // 500;

my @all_squares = map { \$_ * \$_ } ( 2..sqrt \$max );
my @squares = shift @all_squares;
my @out;

CANDIDATE: for my \$candidate ( 1..\$max ) {
if ( @all_squares && \$all_squares[0] == \$candidate) {
push @squares, shift @all_squares;
next CANDIDATE ;
}

for my \$sq ( @squares ) {
next CANDIDATE unless \$candidate % \$sq;
}
push @out, \$candidate;
}

## put output in columns

while (my @temp = splice @out, 1, 10) {
say join ',', map { sprintf "%5s", \$_ } @temp
}

``````

#### Results

``````    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
``````
##### raku solution

In Raku we can use a lazy list for our squares; instead of storing a list we now just store a little piece of whatever code that knows how to make the next square. The whatever code is a closure, and we end up with an iterator that we can shift the next value off of any time we want.

Later on we can make use of the divisibility operator `%%`, which avoids the double-negative of using a modulo for that purpose.

The final output columns first divide the list into groups of 10 elements, then each of those list are given and output format, with a `printf`-style format string and a specified list separator.

``````unit sub MAIN ( \$max = 361 ) ;

my @all-squares =  (2 ... *).map: * ** 2;
my @squares = @all-squares.shift;
my @out;

CANDIDATE: for 1..\$max -> \$candidate {
if @all-squares[0] == \$candidate {
@squares.push: @all-squares.shift;
next CANDIDATE ;
}
\$candidate %% \$_ and next CANDIDATE for @squares;
@out.push: \$candidate;
}

for @out.rotor(10) {
.fmt( "%5s", ',').say
}
``````

The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://theweeklychallenge.org