[seqfan] Re: nice base-dependent sequence

[hv at crypt.org]

Douglas McNeil <mcneil at hku.hk> wrote:
:NJAS:
:
:> Hugo, Douglas, Zak,   Note the current b-file for A177834 (from Robert Gerbicz)
:> has 102 terms.
:
:I'd noticed, and was suitably impressed.  And happy that we agreed on
:the lower ones. :^)
:
:Actually, that reminds me.  At the cost of revealing once again that
:I'm a bear of very little brain, I don't follow Mr Gerbicz's
:description of his sieve, which seems to work beautifully:
:
:> I've used a sieve method to generate the sequence much faster than brute
:> force: find n in the form n=100*x+y, where 0<=y<100 so at once we examine
:> 100 numbers, let x is given, if you fix a string in n and you want to
:> determine the y values for that d|100*x+y, then these y values are in (some)
:> arithmetic progressions.
:
:What about "internal" divisors generated by (say) the last four digits
:of x and the first digit of y?  I don't see how you'd know which
:divisors live directly in the full term "100*x+y" and which live in
:the overlapping subterms created by concatenating x and y.  Or am I
:misunderstanding "fix[ing] a string in n"?  I fell back to brute force
:because unlike a lot of base-related sequences where it's easy to
:construct larger terms from smaller terms, here the possibility of
:internal divisors defeated me utterly, so I'd like to understand what
:I'm missing.  It would probably be useful for many other sequences.

I think the algorithm looks something like this:
  D[] := those divisors not dividing a substring of x
  good[0..99] := 1   # satisfied for all divisors looked at so far
  for each d in D:
    satisfied[0..99] := 0   # satisfied for this divisor
    for each suffix s of x, including zero:
      m := s mod d
      z := if s=0 then d else (-10m mod d)
      while z < 10:
        satisfied[10z .. 10z+9] := 1
        z += d
      y := if s=0 then d else (-100m mod d)
      while y < 100:
        satisfied[y] := 1
        y += d
    for y in 0..99:
      good[y] := good[y] AND satisfied[y]
  for y in 0..99:
    if good[y]:
      report a(n) = 100x+y
      halt
  x := x+1 and repeat

The only operations here involving large numbers are determining D[],
and calculating (s mod d); all other operations can be done with signed
integers k: abs(k) < 100n. In fact, there is no particular reason not
to generalize this to let y be k digits, in which case you could keep
the "large" numbers in 32-bit (or 64-bit) integers much longer before
shifting to a bigint library.

Hugo