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]],
);

[download]

In reply to checking a set of numbers for consistency mod p by hv

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.