Re^2: Faster (but uglier) PWC 350-2 solutions

[Anonymous Monk]

as smarter guys explained, using modulo arithmetic voodoo

Sorry. It's this quote:

The sum of the digits of a number are congruent to the number itself modulo 9. Thus, if A=B*k and A has the same digits as B, then A%9=((B%9)*k)%9.

from here:

https://wlmb.github.io/2025/12/01/PWC350/

He is a scientist, so I trust him :-). E.g. for hex numbers:

my $m = 15;                             # max digit
for my $r ( 0 .. $m ) {                 # remainder
    print "$r:\t";
    for my $w ( 2 .. $m ) {             # witness
        if ( $r == ( $r * $w ) % $m ) {
            print "$w "
        }
    }
    print "\n"
}

# 0:      2 3 4 5 6 7 8 9 10 11 12 13 14 15
# 1:
# 2:
# 3:      6 11
# 4:
# 5:      4 7 10 13
# 6:      6 11
# 7:
# 8:
# 9:      6 11
# 10:     4 7 10 13
# 11:
# 12:     6 11
# 13:
# 14:
# 15:

Easy to see what to skip. Also (everyone), sorry I overcomplicated with @adjust in pwc_px() and ugly_x, the array and adjustment itself should be omitted; it's leftover from previous approach when I tried pre-determined pattern of steps; now step is always "1" and unfriendly numbers explicitly skipped; so just start from $from. Damn ;-). I'm grateful not to have published yesterday; with a few more blunders; hopefully this "@adjust" is the only left

[LanX]

> He is a scientist, so I trust him :-)

Thanks, this makes sense and is indeed connected to the digit sum. :)

(And it's not too hard to understand. But I don't wanna bore you with calculations)

What you are doing is called "sieving", because you apply patterns at repeating steps to avoid futile calculations.

But you could create more complicated sieves

Eg if the first digit is i the max k is 9/i (2-> 4, 3->3, 4->2, 5..9 ->1)

So you can skip looping from 5xxx to 9xxx.

This can be even improved, if the biggest digit is m, max k becomes m/i but that's harder to implement.

Or a k=5 is only possible if you have at least one digit 0 or 5.

Combining all these sieves can get quite complicated and the overhead might not justify it.

But you don't need to search sequentially as long as you cover all integers in an interval.

If you really want to break further speed records inform yourself about techniques of (prime) number searches with sieves.