Tag: perfect squares

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

Submitted by: Mohammad S Anwar

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
}

---