hv has asked for the wisdom of the Perl Monks concerning the following question:
As part of my attempt to find new or improved values for a family of sequences such as https://oeis.org/A292580, I want to know whether a trial assignment of the p-adic order of some or all of a sequence of consecutive integers is consistent for a given prime p.
Eg given a sequence of 5 integers and the prime 2, they could have p-adic orders [0, 1, 0, 2, 0] if the sequence starts at 1, or [1, 0, 5, 0, 1] starting at 30; but they could never look like [2, ?, ?, ?, 2] whatever the starting point: if two multiples of 4 are separated by 4, one of the two must be divisible at least by 8. Similarly [1, 0, 0, 1, 0, 0, 1] with p=3 is not possible.
I've written the function below to answer this question - taking the prime p and an arrayref of known (assigned) p-adic orders with undef representing "unknown", and returning a TRUE value if the set is valid. However it feels very expensive and slow (I expect to call this billions of times), and I feel I must be missing a trick that would give the answer more directly, maybe even with a single pass over the values.
Note that I'm currently typically calling this only with sequences of up to 32 integers, but I'd like as general a solution as possible. However if there's a big win from special-casing p=2 I'd probably take it.
Suggestions for a better algorithm would be much appreciated.
Hugo
sub valid_set { my($p, $known) = @_; my(%seenzero, %seenmore); for my $index (0 .. $#$known) { # look only at the defined values my $power = $known->[$index] // next; if ($power > 0) { # we've seen a power > 0, record its value modulo p ++$seenmore{$index % $p}; } else { # we've seen a power = 0, record its value modulo p ++$seenzero{$index % $p}; } } # the values _not_ divisible by p can be distributed across at mos +t # p - 1 distinct values modulo p return 0 if keys(%seenzero) >= $p; # [update] bugfix: the values that _are_ divisible by p must not have # the same value modulo p as those that are not. Thanks LanX. :) return 0 if grep $seenzero[$_], keys %seenmore; # [end update] # the values that _are_ divisible by p must all have the same valu +e # modulo p return 0 if keys(%seenmore) > 1; my($mod, $seen) = each %seenmore; # if there were no values divisible by p, or exactly one such, we' +re done return 1 if ($seen // 0) <= 1; # else reduce the list to every p'th element, and recurse my @higher; for (my $i = $mod; $i < @$known; $i += $p) { push @higher, defined($known->[$i]) ? $known->[$i] - 1 : undef +; } return valid_set($p, \@higher); } # test the examples: expect [yes, yes, no, no] print valid_set(@$_) ? "yes\n" : "no\n" for ( [ 2, [0, 1, 0, 2, 0]], [ 2, [1, 0, 5, 0, 1]], [ 2, [2, undef, undef, undef, 2]], [ 3, [1, 0, 0, 1, 0, 0, 1]], );
|
|---|