You should also know which primes to expect. Probably all less 32?

In general, any prime p less than the size of the set, ie p should be small enough that it's possible to have 2 entries divisible by p. As you surmise, for the specific case that implies p < 32.

.. provided valid_set() works flawlessly. ;-)

I recommend taking that as given, until you actually find reason to believe it is flawed.

(and later) here my take on it

Thanks, I'll make time today or tomorrow to go through it and try to actually understand your algorithm.

> Thanks, I'll make time today or tomorrow to go through it and try to actually understand your algorithm.

I'd start with automated testing, I'm not 100% sure it holds for all cases with "holes".

update

in hindsight ... it's still producing false negatives:

That's what the algo does with [3, [1, 0, 0, undef, 0, 0, 1]

. . 1 0 0 ? 0 0 1 
0 0 1 0 0 1 0 0 2 0 0 1 0 0 1 0
    ^           *
[download]

That's how it should fit

. . . . . 1 0 0 ? 0 0 1 
0 0 1 0 0 1 0 0 2 0 0 1 0 0 1 0
          ^
[download]

Sorry!

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

If I read it correctly, you currently make a sieve of length 2 * range, centred around p^max. I think you need the length to be around 2 * (range + p^{max - 1}).

I don't understand the logic you're using with $max_pos to decide where in the sieve to match, and I'm not sure it's correct. But I'd be tempted to punt on that - make both sieve and input into strings as below, and use a regexp match.

  use List::Util qw{min};
  my @order = '0' .. '9', 'A' .. 'Z'; # range of 2^36 is probably enou
+gh

  sub to_string {
    my($max, $list) = @_;
    return join '', map {
      defined($_) ? $order[min($_, $max)] : '.'
    } @$list;
  }
[download]