[seqfan] Re: nice base-dependent sequence
hv at crypt.org
hv at crypt.org
Tue Jun 8 14:06:48 CEST 2010
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
More information about the SeqFan
mailing list