# ETOOBUSY đźš€ minimal blogging for the impatient

# PWC138 - Split Number

**TL;DR**

On with TASK #2 from The Weekly Challenge #138. Enjoy!

# The challenge

You are given a perfect square.

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

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`

# The questions

Iâ€™d ask what a *split* is exactly, although the examples allow to make
an educated guess about considering the decimal representation of the
number as a string, and splitting it into parts (two or more, as the
requirement goes).

# The solution

As it often happens, 1 is left out not because itâ€™s not a perfect square
(it is), nor because it canâ€™t be expressed in terms of sum of a split of
its square (it can), but because the split does not include at least two
parts. I guess this is fair for a *split*, less for the 1.

Life sucks, yes, but Iâ€™d like to remember that 1 is the first. Unless you start counting from 0, of course.

Assuming that 1â€™s shoulders are strong enough to be left out of this
lot, the splitting problem is a â€śsolvedâ€ť one, and I suspect in some past
weekly challenge too. Alas, my memory fails me in this, so I just
remember *how* to do it, without the possibility to tell *why* I know
it.

Letâ€™s assume that we have a string representation of a number and that we split it digit by digit, e.g. integer 1296:

```
1 | 2 | 9 | 6
```

To get all possible splits, itâ€™s sufficient to manipulate the different â€śseparatorâ€ť characters above. As an example, if we remove the middle one, we end up with:

```
1 | 2 9 | 6
```

We then join together all sequences without a separator, obtaining partition $(1, 29, 6)$ whose sum is 36. Which, by the way, makes 1296 a match for our test, because $\sqrt{1296} = 36$, yay!

Now, how to generate all possible arrangements of separator characters? The key here is to represent each position where a separator can appear with its own bit: 0 means open, 1 means closed.

At this point, a starting string with $n$ characters will have $n - 1$
possible separators, represented as a sequence of $n - 1$ bits. Nowâ€¦
itâ€™s sufficient to count from 1 (because there must be *at least* one
separator, by requirements) up to $2^n - 1$ and we will get all possible
arrangements. Neat!

Letâ€™s go Perl first this time:

```
#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use List::Util 'sum';
sub split_number ($square) {
my $root = int sqrt $square;
die "invalid input <$square>: not a square"
unless $root * $root == $square;
return 1 if $root =~ m{\A 9+ \z}mxs;
my ($first, @digits) = split m{}mxs, $square;
my $n_separators = @digits;
for my $i (1 .. 2**$n_separators - 1) {
my @split = $first;
my @separators = split m{}mxs, sprintf "%0${n_separators}b", $i;
for my $j (0 .. $#separators) {
if ($separators[$j]) { push @split, $digits[$j] }
else { $split[-1] .= $digits[$j] }
}
return 1 if sum(@split) == $root;
} ## end for my $i (1 .. 2**$n_separators...)
return 0;
} ## end sub split_number ($square)
if (@ARGV) { say split_number($ARGV[0]) }
else {
split_number($_ * $_) && say $_*$_ for 1 .. 1000;
}
```

I knew it. You noticed this line:

```
return 1 if $root =~ m{\A 9+ \z}mxs;
```

Why is that? It turns out that squares of sequences of 9 will *always*
match the requirements, so why bother doing the splits? If you want a
concise proof, just read on.

Letâ€™s define our sequence of 9s as $9_k$:

\[9_k \mathrel{\vcenter{:}}= \underbrace{9..9}_k \equiv 9 \sum_{i=0}^{k-1}10^i \equiv10^k-1\]Now, letâ€™s square it and see what we obtain:

\[\begin{align} (9_k)^2 &= (10^k-1)^2\\ &=10^{2k}-2 \cdot 10^k+1 \\ &= (10^k-2) \cdot 10^k+1 \\ &=\underbrace{9..9}_{k-1}8 \cdot 10^k+1 \\ &= \underbrace{9..9}_{k-1}8\underbrace{0..0}_k + 1 \\ &= \underbrace{9..9}_{k-1}8\underbrace{0..0}_{k-1}1 \end{align}\]Now letâ€™s consider the following split where each 0 is taken individually:

\[\begin{align} \underbrace{9..9}_{k-1}8 + \underbrace{0 + 0 + ... + 0}_{k-1} +1 &= \underbrace{9..9}_{k-1}8+1 \\ &= \underbrace{9..9}_k \\ &= 9_k \end{align}\]So, $(9_k)^2$ is indeed a square with a split of 2 or more parts whose sum amounts to its root $9_k$.

Raku time now:

```
#!/usr/bin/env raku
use v6;
sub split-number (Int:D $square) {
my $root = $square.sqrt.Int;
die "invalid input <$square>: not a square"
unless $root * $root == $square;
return 1 if $root ~~ /^ 9+ $/;
my ($first, @digits) = $square.comb: /./;
my $n-separators = @digits.elems;
for 1 ..^ 2**$n-separators -> $i {
my @split = $first,;
my @separators = $i.base(2).comb: /./;
@separators.unshift: 0 while @separators.elems < $n-separators;
for 0 .. @separators.end -> $j {
if @separators[$j] > 0 { @split.push: @digits[$j] }
else { @split[*-1] ~= @digits[$j] }
}
return 1 if @split.sum == $root;
} ## end for my $i (1 .. 2**$n_separators...)
return 0;
}
sub MAIN (*@args) {
if @args { split-number(@args[0]).put }
else {
my @sequence = (1...Inf).map({$_**2}).grep({split-number($_) > 0});
@sequence[0..^10].join(', ').put;
}
}
```

This translation from Perl proved to be trickier than expected.
Evaluating an array in â€śscalar contextâ€ť does not do what Iâ€™m used to in
Perl, which hit me a couple of times. Additionally, the whole
`sprintf`

stuff in Perl was not working and I had to use a
combination of base change, `comb`

ing and putting enough leading 0
characters in the result to match the needed amount of bits. Whew!

I guess this is it for this entryâ€¦ thanks and stay safe!