If you do a
print $num & $shift ? '+' : '.' ; in the loop (following diotalevi's example), you can observer for $num (0..20) the pattern:
........................
+.......................
.+......................
++......................
..+.....................
+.+.....................
.++.....................
+++.....................
...+....................
+..+....................
.+.+....................
++.+....................
..++....................
+.++....................
.+++....................
++++....................
....+...................
+...+...................
.+..+...................
++..+...................
..+.+...................
And the middle part (8388608..8388628):
.......................+
+......................+
.+.....................+
++.....................+
..+....................+
+.+....................+
.++....................+
+++....................+
...+...................+
+..+...................+
.+.+...................+
++.+...................+
..++...................+
+.++...................+
.+++...................+
++++...................+
....+..................+
+...+..................+
.+..+..................+
++..+..................+
..+.+..................+
And the end part (16777196..16777216):
..++.+++++++++++++++++++
+.++.+++++++++++++++++++
.+++.+++++++++++++++++++
++++.+++++++++++++++++++
....++++++++++++++++++++
+...++++++++++++++++++++
.+..++++++++++++++++++++
++..++++++++++++++++++++
..+.++++++++++++++++++++
+.+.++++++++++++++++++++
.++.++++++++++++++++++++
+++.++++++++++++++++++++
...+++++++++++++++++++++
+..+++++++++++++++++++++
.+.+++++++++++++++++++++
++.+++++++++++++++++++++
..++++++++++++++++++++++
+.++++++++++++++++++++++
.+++++++++++++++++++++++
++++++++++++++++++++++++
........................
Looks like a sparse matrix we could explore. Like, if you add
if ($num<$shift){$total-=(24-$i)*(25+$i)/2; last;} in the loop, it would speed up the beginning of the loop (but slow down the end). Here a sample code (mostly diotalevi's):
#!/usr/bin/perl -w
use strict;
use integer;
my $ans = 0;
for my $num (0..16777216) {
my $total = 0;
my $shift = 1;
for my $i (1..24) {
$total += $num & $shift ? $i : -$i;
if ($num<$shift){$total-=(24-$i)*(25+$i)/2; last;}
$shift <<= 1;
}
$ans++ if $total == 0;
}
print $ans;
Ironically, I mostly found out how to slow the code down rather than speeding it up.
Though the
$shift <<= 1; part is essentially static and equivalent to
@shift = qw/ 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 /;, using array will slow things down.
If you want something even
slower, here is something I tried in Pari:
#!/usr/bin/perl -w
use Math::Pari qw/ PARI / ;
PARI 'ans=0' ;
my $cmd = qq/
for(
num = 0, 1677,
total=0; shft=1;
for(
i = 1, 24,
if(bitand(num,shft)==0, total+=-i, total+=i);
shft <<= 1;
);
if(total==0, ans++);
)
/;
$cmd =~ s/\s//g;
PARI $cmd ;
print PARI('ans');
Funny enough, it's slow as CDROM.