Peter
Peter Campbell Smith

Working years
and square sums

Weekly challenge 138 — 8 November 2021

Week 138: 8 Nov 2021

Task 2

Task — Split number

You are given a perfect square $square. Write a script to figure out if the square root of $square is same as sum of 2 or more splits of the given number.

Examples


Example 1
Input: $n = 81
Output: 1, since sqrt(81) = 8 + 1

Example 2
Input: $n = 9801
Output: 1, since sqrt(9801) = 98 + 0 + 1

Example 3
Input: $n = 36
Output: 0, since sqrt(36) != 3 + 6

Analysis

The slightly tricky requirement is to generate all the splits of a multi-digit number (eg 123456).

Consider the number as a string of $n digits. Consider also a binary number with $n - 1 digits (eg 01101). If we generate all such binary numbers, and consider each bit to represent whether the corresponding digit in the split is followed by ' + ', we can generate all the splits.

So for example 123456 and 01101 yields 12 + 3 + 45 + 6: a plus has been inserted after the first, second and fifth digits of $n because the first, second and fifth bits of the binary number are 1.

Once we have all the splits we can eval them to get the sum, and compare it with sqrt($n).

There is one slight catch. If $n contains am embedded 0 (eg 123056) then we will get splits like 123 + 056. Perl regards 056 as octal 56, so it is necessary to remove these leading zeroes before the eval.

Try it 

Try running the script with any input:



example: 6724

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2021-11-08
# PWC 138 task 2

use v5.20;
use warnings;
use strict;

my (@squares, $square, $root, $gaps, $plus_map, $position, $result, $sum, $since, $good, 
    $legend0, $legend1, $result2);

# test values
@squares = (81, 9801, 36 ** 2, 45 ** 2, 55 ** 2, 82 ** 2, 91 ** 2, 92 ** 2, 777 ** 2);

# loop over test values
for $square (@squares) {
    
    # check it really is a sqare
    $root = sqrt($square);
    say qq[Input: $square ($root ** 2)];
    if ($root != int($root) or $square < 10) {
        say qq[$square is not an integer square >= 10\n];
        next;
    }
    
    # initialisation
    $gaps = length($square) - 1;   # no of gaps where we could insert a +
    $good = 0;
    $since = '';
    $legend1 = qq[Output: 1\nsince];
    $legend0 = qq[Output: 0\nsince];
    
    # loop over binary numbers eg if $gaps == 6, from 000001 to 111111
    for $plus_map (1 .. 2 ** $gaps - 1) {
        
        # create a string containing pluses in the appropriate places (eg 123 + 456)
        $result = '';
        for $position (0 .. $gaps) {
            $result .= substr($square, $position, 1);
            if ($plus_map & (2 ** $position)) {   # use bitwise & to isolate the appropriate bit
                $result .= ' + ';
            }
        }
        
        # need to avoid constructs like + 012 as perl regards 012 as an octal number
        $result2 = $result;
        $result2 =~ s| 0(\d)| $1|g;
        
        # evaluate the string
        $sum = eval($result2);
        
        # good result - sums to the root of the original number - show it
        if ($sum == $root) {
            say qq[$legend1 $result == $sum];
            $good = 1;
            $legend1 = 'and  ';
            
        # bad result - it doesn't; keep this in $since in case no good result is found
        } else {
            $since .= qq[$legend0 $result == $sum != $root\n];
            $legend0 = 'and  ';
        }
    }
    
    # if there were no good results, list the bad ones
    print $good ? qq[\n] : qq[$since\n];
}

Output


Input: 81 (9 ** 2)
Output: 1
since 8 + 1 == 9

Input: 9801 (99 ** 2)
Output: 1
since 98 + 01 == 99
and   98 + 0 + 1 == 99

Input: 1296 (36 ** 2)
Output: 1
since 1 + 29 + 6 == 36

Input: 2025 (45 ** 2)
Output: 1
since 20 + 25 == 45

Input: 3025 (55 ** 2)
Output: 1
since 30 + 25 == 55

Input: 6724 (82 ** 2)
Output: 1
since 6 + 72 + 4 == 82

Input: 8281 (91 ** 2)
Output: 1
since 8 + 2 + 81 == 91
and   82 + 8 + 1 == 91

Input: 8464 (92 ** 2)
Output: 0
since 8 + 464 == 472 != 92
and   84 + 64 == 148 != 92
and   8 + 4 + 64 == 76 != 92
and   846 + 4 == 850 != 92
and   8 + 46 + 4 == 58 != 92
and   84 + 6 + 4 == 94 != 92
and   8 + 4 + 6 + 4 == 22 != 92

Input: 603729 (777 ** 2)
Output: 0
since 6 + 03729 == 3735 != 777
and   60 + 3729 == 3789 != 777
and   6 + 0 + 3729 == 3735 != 777
and   603 + 729 == 1332 != 777
and   6 + 03 + 729 == 738 != 777
and   60 + 3 + 729 == 792 != 777
and   6 + 0 + 3 + 729 == 738 != 777
and   6037 + 29 == 6066 != 777
and   6 + 037 + 29 == 72 != 777
and   60 + 37 + 29 == 126 != 777
and   6 + 0 + 37 + 29 == 72 != 777
and   603 + 7 + 29 == 639 != 777
and   6 + 03 + 7 + 29 == 45 != 777
and   60 + 3 + 7 + 29 == 99 != 777
and   6 + 0 + 3 + 7 + 29 == 45 != 777
and   60372 + 9 == 60381 != 777
and   6 + 0372 + 9 == 387 != 777
and   60 + 372 + 9 == 441 != 777
and   6 + 0 + 372 + 9 == 387 != 777
and   603 + 72 + 9 == 684 != 777
and   6 + 03 + 72 + 9 == 90 != 777
and   60 + 3 + 72 + 9 == 144 != 777
and   6 + 0 + 3 + 72 + 9 == 90 != 777
and   6037 + 2 + 9 == 6048 != 777
and   6 + 037 + 2 + 9 == 54 != 777
and   60 + 37 + 2 + 9 == 108 != 777
and   6 + 0 + 37 + 2 + 9 == 54 != 777
and   603 + 7 + 2 + 9 == 621 != 777
and   6 + 03 + 7 + 2 + 9 == 27 != 777
and   60 + 3 + 7 + 2 + 9 == 81 != 777
and   6 + 0 + 3 + 7 + 2 + 9 == 27 != 777

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain