in reply to Faster (but uglier) PWC 350-2 solutions

As usual the task is mathematically unclean and contradicts the example ¹

from https://theweeklychallenge.org/blog/perl-weekly-challenge-350/#TASK2

That's wrong since the rules explicitly allow A = B and k = 1.

Hence all integers belong to at least one shuffle pair. ²

> Further, as smarter guys explained, using modulo arithmetic voodoo, a lot of unfriendly numbers (which can't have any pals anyway) should simply be skipped;

Yes there are many possible filters to skip "unfriendly" integers which come to mind after excluding k=1.

But it would have been helpful if you expressed those rules in written words, instead of letting us reverse engineer them from your code.

update

Which seem to be based on the digit sum rules of integers divisible by 3 and 9.

For instance:

Since shuffling doesn't change the digit sum, B must also be divisible by 3 and 9 iff A is.

Hence all k from {3,6,9} can be excluded for As not divisible by 3, because B=A*k is.

Number theory is a bit strong a name, digit sum rules were already taught in elementary school.

footnotes

¹) It's also unclear of digits can appear multiple times. All examples seem to indicate no. But those solutions exist, for instance if A and B are pairs, so are A.Õ and B.Õ with Õ being a sequence of 0 of arbitrary length.

²) I was wrong, see correction in choroba's reply.

Cheers Rolf
(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery

Replies are listed 'Best First'.
Re^2: Faster (but uglier) PWC 350-2 solutions
by choroba (Cardinal) on Dec 09, 2025 at 15:50 UTC
    I'm responsible for the wording. It definitely has some flaws, but it doesn't allow for the witness to be 1, because of but in different orders.

    Digits can be repeated, and such cases do appear in the examples. Namely, in Example 4, we have 2 * 14002857 = 28005714 where the 0 is repeated twice. (Can you find the second occurrence?)

    map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
[reply]
[d/l]
[select]
      > but in different orders.

      My bad, I stand corrected. But writing A < B from the beginning would have been better.

      > Namely, in Example 4,

      does only give the number of occurrences not that explicit result you showed.

      Without calculating the numbers for both interpretations, it's not possible to tell which one is right, if you suspect that the wording is flawed.

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      see Wikisyntax for the Monastery

[reply]
[d/l]
        > But writing A < B from the beginning would have been better.

        That would need me to think about it more than I did. ;-)

        > Without calculating the numbers for both interpretations, it's not possible

        That's how the Weekly Challenge often works. Sometimes, even the examples don't give enough clues and people come with different interpretations. That's part of the fun.

        map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
[reply]
[d/l]
Re^2: Faster (but uglier) PWC 350-2 solutions
by Anonymous Monk on Dec 09, 2025 at 17:46 UTC
    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:

    [download]

    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

[reply]
[d/l]
[select]
      > 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.

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      see Wikisyntax for the Monastery

[reply]

In Section Seekers of Perl Wisdom