A005360 complete?

[Maximilian Hasler]

[Flimsy numbers.]

On Sun, Jul 13, 2008 at 17:12, Richard Mathar <mathar at strw.leidenuniv.nl>
wrote:

> I think that a=37 is missing in A005360 (and therefore
> to be removed from A125121) because with k=7085 we
> have the binary representations
> 37=[1, 0, 1, 0, 0, 1]
> 37*k= [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
>
> The same problem occurs with 74, 83, and 101, all to be added to A005360
> and to be removed from A125121.
>
> The main question is: is there an algorithm to demonstrate
> absence of numbers in A005360? (The above were found by a
> brute-force scan with some arbitrary upper k=30000.)


Without much thinking, one can make several simple statements

1/ if  M is flimsy, then M*2^m is flimsy for every m

2/ more generally, if M is flimsy and d is less or equal than the distance
of any two nonzero bits of M or of k*M (having less bits than M), then M *
2^m * t is flimsy for any m and any t less than 2^d.
Example: d=2 for M=37 (distance of the 2 highest bits of 37), so M * 2^m * t
is flimsy for t=1,2,3.

3/ an algorithm that might be a bit more efficient than the most naive scan,
especially for numbers not having many bits set, could be based on the idea
to consider only numbers with less bits than M, and to check if they are
multiples of M.
e.g., for M=37 with B(M)=3 nonzero bits, only numbers with 2 bits set need
to be checked ;
furthermore, only odd numbers need to be checked,
(if M=(2t+1)*2^m is not odd, then it is flimsy iff (2t+1) is)
so in the present case, it is sufficient to scan only the numbers of the
form 1+2^m > 37.

Maximilian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20080714/d20c2d21/attachment.htm>