Faster (but uglier) PWC 350-2 solutions

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

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

Looks like the consensus on how to approach this would be to "split, sort, join" to generate keys for finding pair pals. 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; and, of those that remain, it's pointless to ask some of the witnesses about, i.e skip these witnesses, too. So, my subroutine to solve the problem is:

sub pwc {
    my ( $from, $to, $target ) = @_;
    
    use integer;
    my @witnesses = ([ 4, 7 ], [ 2 .. 9 ]);

    my ( %pairs, $j );
    for ( my $i = ( $from + 2 ) / 3 * 3; $i <= $to; $i += 3 ) {
        my $i_key = join '', sort split '', $i;
        my $k = $i % 9 ? 0 : 1;
        
        for ( @{ $witnesses[ $k ]}) {
            last if length( $j = $i * $_ ) != length( $i );
            $pairs{ $i }{ $j } = $_
                unless $i_key ne join '', sort split '', $j
        }
        for ( @{ $witnesses[ $k ]}) {
            last if length( $j = $i / $_ ) != length( $i );
            $pairs{ $i }{ $j } = -$_
                unless $i % $_
                    || exists $pairs{ $j } && 
                       exists $pairs{ $j }{ $i }
                    || $i_key ne join '', sort split '', $j
        }
    }
    return scalar grep { %$_ >= $target } values %pairs
}
[download]

However, even though some solutions mention "speed", I haven't seen optimizations which follow. First, if using CPAN modules is OK (and why not), almost exactly twice as fast is to sort in-place instead:

use Sort::Packed 'sort_packed';

sub pwc_p {
    my ( $from, $to, $target ) = @_;
    
    use integer;
    my @witnesses = ([ 4, 7 ], [ 2 .. 9 ]);
    
    my ( %pairs, $j );
    for ( my $i = ( $from + 2 ) / 3 * 3; $i <= $to; $i += 3 ) {
        sort_packed C => my $i_key = $i;
        my $k = $i % 9 ? 0 : 1;
        
        for ( @{ $witnesses[ $k ]}) {
            last if length( $j = $i * $_ ) != length( $i );
            sort_packed C => my $j_key = $j;
            $pairs{ $i }{ $j } = $_
                unless $i_key ne $j_key
        }
        for ( @{ $witnesses[ $k ]}) {
            last if length( $j = $i / $_ ) != length( $i );
            next if $i % $_;
            sort_packed C => my $j_key = $j;
            $pairs{ $i }{ $j } = -$_
                unless exists $pairs{ $j } && 
                       exists $pairs{ $j }{ $i }
                    || $i_key ne $j_key
        }
    }
    return scalar grep { %$_ >= $target } values %pairs
}
[download]

Secondly, in theory (as far as I can pretend to know it), sorting is O(NlogN), but histogramming should, I guess, be O(N); but, seriously, more important in practice, the latter can be aborted as soon as mismatch is detected:

sub ugly {
    my ( $from, $to, $target ) = @_;
    
    use integer;
    my @witnesses = ([ 4, 7 ], [ 2 .. 9 ]);
    
    my ( %pairs, $j );
    for ( my $i = ( $from + 2 ) / 3 * 3; $i <= $to; $i += 3 ) {
        my $k = $i % 9 ? 0 : 1;
        
        for ( @{ $witnesses[ $k ]}) {
            last if length( $j = $i * $_ ) != length( $i );
            $pairs{ $i }{ $j } = $_
                unless $i =~ tr/12// != $j =~ tr/12//
                    || $i =~ tr/34// != $j =~ tr/34//
                    || $i =~ tr/56// != $j =~ tr/56//
                    || $i =~ tr/78// != $j =~ tr/78//
                    || $i =~ tr/9//  != $j =~ tr/9// 
                    || $i =~ tr/2//  != $j =~ tr/2// 
                    || $i =~ tr/4//  != $j =~ tr/4// 
                    || $i =~ tr/6//  != $j =~ tr/6// 
                    || $i =~ tr/8//  != $j =~ tr/8//
        }
        for ( @{ $witnesses[ $k ]}) {
            last if length( $j = $i / $_ ) != length( $i );
            $pairs{ $i }{ $j } = -$_
                unless $i % $_ 
                    || exists $pairs{ $j } && 
                       exists $pairs{ $j }{ $i }
                    || $i =~ tr/12// != $j =~ tr/12//
                    || $i =~ tr/34// != $j =~ tr/34//
                    || $i =~ tr/56// != $j =~ tr/56//
                    || $i =~ tr/78// != $j =~ tr/78//
                    || $i =~ tr/9//  != $j =~ tr/9// 
                    || $i =~ tr/2//  != $j =~ tr/2// 
                    || $i =~ tr/4//  != $j =~ tr/4// 
                    || $i =~ tr/6//  != $j =~ tr/6// 
                    || $i =~ tr/8//  != $j =~ tr/8//
        }
    }
    return scalar grep { %$_ >= $target } values %pairs
}
[download]

Let's see:

say "$^V / $Config{ archname } / $Config{ gccversion }";

cmpthese -3, {
    pwc   => sub { pwc( 1500, 2500, 1 )},
    pwc_p => sub { pwc_p( 1500, 2500, 1 )},
    ugly  => sub { ugly( 1500, 2500, 1 )},
};

# v5.32.1 / MSWin32-x64-multi-thread / 8.3.0
#         Rate   pwc pwc_p  ugly
# pwc    737/s    --  -48%  -77%
# pwc_p 1424/s   93%    --  -56%
# ugly  3251/s  341%  128%    --
[download]

Well, considering that many PWC solutions don't skip neither numbers nor witnesses (i.e. check them all), and, e.g., some of them sort (for, remember, split-sort-join procedure) numerically (which is noticeably slower), etc. -- i.e. most are already, ehm, not as fast as the "pwc" subroutine above -- then the speed of "ugly" has "order-of-magnitude-class" advantage which is quite astonishing, I think.

-------

Maybe it's curious, but hex numbers can have pals too, of course. E.g., going from 0x1DEA to 0xC0DE encounters 89 shuffle-prone numbers, among them 2 more gregarious hexadecimals with exactly 2 pals each:

  "2490" => { 4920 => 2, 9240 => 4 },
  "3b10" => { "13b0" => -3, "b130" => 3 },
[download]

(extracted from output of Data::Dump::dd( \%pairs );.) Modulo voodoo logic, i.e. significant speed-up, by which to skip numbers and whether to call in witnesses for those which remain, is the same:

sub pwc_px {
    my ( $from, $to, $target ) = @_;
    
    use integer;
#                     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
    my @adjust  = qw/ 0  2  1  0  1  0  0  2  1  0  0  1  0  2  1 /;
    $from += $adjust[ $from % 15 ];

    my @witnesses = ([ 6, 11 ], [ 4, 7, 10, 13 ], [ 2 .. 15 ]);

    my ( %pairs, $jx );
    for my $i ( $from .. $to ) {
        next if $i % 3 and $i % 5;

        my $k = $i % 15 ? $i % 5 ? 0 : 1 : 2;
        
        my $ix = sprintf '%x', $i;
        sort_packed C => my $i_key = $ix;
        for ( @{ $witnesses[ $k ]}) {
            $jx = sprintf '%x', $i * $_;
            last if length( $jx ) != length( $ix );
            sort_packed C => my $j_key = $jx;
            $pairs{ $ix }{ $jx } = $_ 
                unless $i_key ne $j_key
        }
        for ( @{ $witnesses[ $k ]}) {
            $jx = sprintf '%x', $i / $_;
            last if length( $jx ) != length( $ix );
            next if $i % $_;
            sort_packed C => my $j_key = $jx;
            $pairs{ $ix }{ $jx } = -$_
                unless exists $pairs{ $jx } && 
                       exists $pairs{ $jx }{ $ix }
                    || $i_key ne $j_key
        }
    }
    return scalar grep { %$_ >= $target } values %pairs
}

sub ugly_x {
    my ( $from, $to, $target ) = @_;
    
    use integer;
#                     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
    my @adjust  = qw/ 0  2  1  0  1  0  0  2  1  0  0  1  0  2  1 /;
    $from += $adjust[ $from % 15 ];

    my @witnesses = ([ 6, 11 ], [ 4, 7, 10, 13 ], [ 2 .. 15 ]);

    my ( %pairs, $jx );
    for my $i ( $from .. $to ) {
        next if $i % 3 and $i % 5;
        
        my $k = $i % 15 ? $i % 5 ? 0 : 1 : 2;
        
        my $ix = sprintf '%x', $i;
        for ( @{ $witnesses[ $k ]}) {
            $jx = sprintf '%x', $i * $_;
            last if length( $jx ) != length( $ix );
            $pairs{ $ix }{ $jx } = $_
                unless $ix =~ tr/1// != $jx =~ tr/1//
                    || $ix =~ tr/2// != $jx =~ tr/2//
                    || $ix =~ tr/3// != $jx =~ tr/3//
                    || $ix =~ tr/4// != $jx =~ tr/4//
                    || $ix =~ tr/5// != $jx =~ tr/5//
                    || $ix =~ tr/6// != $jx =~ tr/6//
                    || $ix =~ tr/7// != $jx =~ tr/7//
                    || $ix =~ tr/8// != $jx =~ tr/8//
                    || $ix =~ tr/9// != $jx =~ tr/9//
                    || $ix =~ tr/a// != $jx =~ tr/a//
                    || $ix =~ tr/b// != $jx =~ tr/b//
                    || $ix =~ tr/c// != $jx =~ tr/c//
                    || $ix =~ tr/d// != $jx =~ tr/d//
                    || $ix =~ tr/e// != $jx =~ tr/e//
                    || $ix =~ tr/f// != $jx =~ tr/f//
        }
        for ( @{ $witnesses[ $k ]}) {
            $jx = sprintf '%x', $i / $_;
            last if length( $jx ) != length( $ix );
            $pairs{ $ix }{ $jx } = -$_
                unless $i % $_ 
                    || exists $pairs{ $jx } && 
                       exists $pairs{ $jx }{ $ix }
                    || $ix =~ tr/1// != $jx =~ tr/1//
                    || $ix =~ tr/2// != $jx =~ tr/2//
                    || $ix =~ tr/3// != $jx =~ tr/3//
                    || $ix =~ tr/4// != $jx =~ tr/4//
                    || $ix =~ tr/5// != $jx =~ tr/5//
                    || $ix =~ tr/6// != $jx =~ tr/6//
                    || $ix =~ tr/7// != $jx =~ tr/7//
                    || $ix =~ tr/8// != $jx =~ tr/8//
                    || $ix =~ tr/9// != $jx =~ tr/9//
                    || $ix =~ tr/a// != $jx =~ tr/a//
                    || $ix =~ tr/b// != $jx =~ tr/b//
                    || $ix =~ tr/c// != $jx =~ tr/c//
                    || $ix =~ tr/d// != $jx =~ tr/d//
                    || $ix =~ tr/e// != $jx =~ tr/e//
                    || $ix =~ tr/f// != $jx =~ tr/f//
        }
    }
    return scalar grep { %$_ >= $target } values %pairs
}


cmpthese -3, {
    pwc_px => sub { pwc_px( 0x1DEA, 0xC0DE, 2 )},
    ugly_x => sub { ugly_x( 0x1DEA, 0xC0DE, 2 )},
};

#          Rate pwc_px ugly_x
# pwc_px 23.1/s     --   -38%
# ugly_x 37.2/s    61%     --
[download]

Heh, ugly solution with lots of copy-n-paste'd lines is faster. And, I guess I'd better not publish even uglier code with not 15, but 35 such lines -- to avoid offending someone because of, actually, duplicating the above with very obvious changes -- moving to base 36 and ntheory::todigitstring( $i, 36 ) instead of sprintf( '%x', $i ), and:

@witnesses = ([ 8, 15, 22, 29 ], [ 6, 11, 16, 21, 26, 31 ], [ 2 .. 35 
+]);
[download]

E.g., going from 36#idea to 36#perl finds 17 pairs, all through division this time, interestingly (did I mention negatives are to indicate division?). And an "interesting" fat witness, too (10#19 i.e. 36#j):

{
  j376 => { "36j7" => -6 },
  j736 => { "376j" => -6 },
  k03c => { "3c0k" => -6 },
  k12c => { "1c2k" => -15 },
  k3c0 => { "3ck0" => -6 },
  lm3o => { "3lom" => -6 },
  m3lo => { "3olm" => -6 },
  n174 => { "17n4" => -19 },
  n840 => { "4n80" => -5 },
  nbco => { bnoc => -2 },
  o029 => { "2o09" => -9 },
  o290 => { "2o90" => -9 },
  o4dt => { "4tod" => -5 },
  onbc => { cbno => -2 },
  p046 => { "460p" => -6 },
  p460 => { "46p0" => -6 },
  pb6s => { "6bsp" => -4 },
}

***
          Rate pwc_p36 ugly_36
pwc_p36 2.02/s      --    -14%
ugly_36 2.36/s     17%      --
[download]

with the ugly thing still faster

Comment on Faster (but uglier) PWC 350-2 solutions Select or Download Code

Replies are listed 'Best First'.
Re: Faster (but uglier) PWC 350-2 solutions by ysth (Canon) on Dec 09, 2025 at 21:51 UTC
FWIW my solution just limits the range of witnesses: `for my $witness (2..int((10*length($i) - 1) / $i)) { if ($i_sorted eq join '', sort split //, $i $witness) { if (++$pairs == $count) { ++$qualifying_integers; next I; } } } # maximum witness can't be more than i's first digit for my $witness (2..substr $i, 0, 1) { if (!( $i % $witness ) && $i_sorted eq join '', sort split + //, $i / $witness) { if (++$pairs == $count) { ++$qualifying_integers; next I; } } }` [download] and tries to limit the ops executed in the loop body. To take advantage of other witness elimination, you'd unwrap the outer loop and have special code for e.g multiples of 3, but that if a lot of duplication. You'd get a much better speed bump using Inline for at least the "does it have the same digits" check. My go solution is much much faster. But all the conversions from numbers to strings to runes make it a lot longer. Python was interesting; it lacks the ability to continue an outer loop, so the two inner loop approach needed an additional flag variable. But Python's iterator design made a single inner loop possible, at a slight speed penalty but producing the tersest code.	[reply] [d/l]
Re^2: Faster (but uglier) PWC 350-2 solutions by Anonymous Monk on Dec 10, 2025 at 16:01 UTC
You'd get a much better speed bump using Inline for at least the "does it have the same digits" check. No. Chained transliterations are too trivial, any subroutine (or C function) call seems more expensive. Results are not too different with "return 1" line uncommented. use Inline C => <<'END_OF_C'; int histcmp( SV* sv1, SV* sv2 ) { // return 1; STRLEN len; char* s1 = SvPVbyte( sv1, len ); char* s2 = SvPVbyte( sv2, len ); char h1[ 10 ]; char h2[ 10 ]; memset( h1, 0, sizeof( h1 )); memset( h2, 0, sizeof( h2 )); for ( int i = 0; i < len; i ++ ) { h1[ s1[ i ] - '0' ] ++; h2[ s2[ i ] - '0' ] ++; } return memcmp( h1, h2, 10 ); } END_OF_C sub pwc_c { my ( $from, $to, $target ) = @_; use integer; my @witnesses = ([ 4, 7 ], [ 2 .. 9 ]); my ( %pairs, $j ); for ( my $i = ( $from + 2 ) / 3 * 3; $i <= $to; $i += 3 ) { my $k = $i % 9 ? 0 : 1; for ( @{ $witnesses[ $k ]}) { last if length( $j = $i * $_ ) != length( $i ); $pairs{ $i }{ $j } = $_ unless histcmp( $i, $j ) } for ( @{ $witnesses[ $k ]}) { last if length( $j = $i / $_ ) != length( $i ); $pairs{ $i }{ $j } = -$_ unless $i % $_ \|\| exists $pairs{ $j } && exists $pairs{ $j }{ $i } \|\| histcmp( $i, $j ) } } return scalar grep { %$_ >= $target } values %pairs } cmpthese -3, { pwc_c => sub { pwc_c( 1500, 2500, 1 )}, ugly => sub { ugly( 1500, 2500, 1 )}, }; cmpthese -3, { pwc_c => sub { pwc_c( 13_427_000, 14_100_000, 2 )}, ugly => sub { ugly( 13_427_000, 14_100_000, 2 )}, }; # Rate pwc_c ugly # pwc_c 2865/s -- -12% # ugly 3251/s 13% -- # Rate pwc_c ugly # pwc_c 3.42/s -- -9% # ugly 3.75/s 10% -- [download]	[reply] [d/l]
Re^2: Faster (but uglier) PWC 350-2 solutions by LanX (Saint) on Dec 10, 2025 at 00:09 UTC
In the first loop you check for $i being A and in the second for $i being B hence `$i / $witness` . That's a different interpretation� of the task `B = A * k` , the OP was only doing the A part. Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery} �) According to Choroba that's the fun part of PWC ;-)	[reply] [d/l] [select]
Re^3: Faster (but uglier) PWC 350-2 solutions by ysth (Canon) on Dec 10, 2025 at 00:46 UTC
None of the examples involve finding A given B, but that just means they work either way. But to me the problem statement is clear: "the number of integers $i in the range $from <= $i <= $to that belong to at least $count different shuffle pairs".	[reply]
Re^4: Faster (but uglier) PWC 350-2 solutions by LanX (Saint) on Dec 10, 2025 at 02:05 UTC
Re^2: Faster (but uglier) PWC 350-2 solutions by Anonymous Monk on Dec 10, 2025 at 18:19 UTC
My go solution is much much faster. How much (if I may)? I've never run Go nor have it; at ATO (can link if requested), your Go function runs in ~600 mks and ~900 ms for Examples 2 and 4 arguments respectively. I know it's a silly test. Perl results from my previous answer, for the same args, are better when run locally at rather old PC	[reply]
Re^2: Faster (but uglier) PWC 350-2 solutions by Anonymous Monk on Dec 09, 2025 at 23:12 UTC
I think if in e.g. "Example 2" the `$to` was e.g. 8500, then your solution would find all 3 pairs again and report false positives. I.e. stronger accounting is required. I'm not sure I'm happy with my own accounting, on the 2nd thought. If `$count` in "Example 3" was not "5" but "1", then how many items would be added to the result for "1428570"? 1 or 5? The "at least" in the wording of the challenge seems to imply that "1". Or such is my interpretation (PWC ambiguous as usual). But then it follows, that you can't break out early with "`next I;`". Because there will be false positives later if `$to` was higher (see?). I had a similar "`next OUTER;`" in initial drafts, but then decided against it.	[reply] [d/l] [select]
Re^3: Faster (but uglier) PWC 350-2 solutions by ysth (Canon) on Dec 09, 2025 at 23:42 UTC
I don't know what you mean by false positives? The test is how many numbers in the range are part of at least count pairs. Having both ends of a pair in the range just means both numbers count. And each number only counts once. Can you explain what you think is ambiguous? (Agreed that PWC often is; usually the examples clarify, but not always.)	[reply]
Re^4: Faster (but uglier) PWC 350-2 solutions by Anonymous Monk on Dec 10, 2025 at 10:11 UTC
Re: Faster (but uglier) PWC 350-2 solutions by LanX (Saint) on Dec 09, 2025 at 14:09 UTC
As usual the task is mathematically unclean and contradicts the example � from https://theweeklychallenge.org/blog/perl-weekly-challenge-350/#TASK2 If two integers A <= B have the same digits but in different orders, we say that they belong to the same shuffle pair if and only if there is an integer k such that B = A * k where k is called the witness of the pair. ... Example 1: `Input: $from = 1, $to = 1000, $count = 1 Output: 0 There are no shuffle pairs with elements less than 1000.` [download] ~~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}	[reply] [d/l] [select]
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]
Re^3: Faster (but uglier) PWC 350-2 solutions by LanX (Saint) on Dec 09, 2025 at 16:01 UTC
> 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]
Re^4: Faster (but uglier) PWC 350-2 solutions by choroba (Cardinal) on Dec 09, 2025 at 16:56 UTC
Re^5: Faster (but uglier) PWC 350-2 solutions by LanX (Saint) on Dec 09, 2025 at 19:17 UTC
Some notes below your chosen depth have not been shown here
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=Bk 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]
Re^3: Faster (but uglier) PWC 350-2 solutions by LanX (Saint) on Dec 09, 2025 at 19:10 UTC
> 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]

update

footnotes