[seqfan] Re: Sturdy and flimsy numbers.

[franktaw at netscape.net]

Another approach is to try to create the multiplier one bit at a time.  
(First, divide out an factors of 2.)  Start with a 1 as the low-order 
bit of the multiplier; this gives us 1 bit on in the product, and 
floor(n/2) as the carry.  At each subsequent bit, we get two possible 
factors, for a 0 or a 1 bit in the multiplier.  Each gives us a certain 
number of bits in the product, and a carry less than N.  If the number 
of 1 bits is >= the number of 1's in N, or if the carry has been seen 
before with the same or smaller number of 1's in the product, that path 
can be abandoned.  If the carry is zero, the number is flimsy, and you 
have found an example -- with a little care in the order in which you 
do things, it will be the smallest example.  (Actually, you can look at 
the number of 1's so far in the product plus the number in the carry, 
and stop if that is <= the number of 1's in N.)

This likewise shows that the problem is finite.  I think the time 
requirement is on the same order as Jack's algorithm -- both should be 
O(N).

-----
There should perhaps be sequences in the database for odd flimsy and 
sturdy numbers, since 2n is flimsy iff n is.

-----
One can ask similar questions for other bases.  There are two obvious 
variants:

Is there a multiple of N with a smaller sum of digits in base b than N 
has?

Is there a multiple of N with fewer non-zero digits in base b than N 
has?

Franklin T. Adams-Watters

-----Original Message-----
From: T. D. Noe <noe at sspectra.com>

>I followed an A-number from one frame of the OEIS movie,
>and found this:
>http://www.research.att.com/~njas/sequences/A125121
>
>
>Just wondering, how well-defined this kind of sequence is?
>
>That is, is there some absolute upper limit of k for each n,
>after which the program can finish the testing loop?

Although theorem 2.1 in the paper by Stolarsky is useful, the seqfan 
e-mail
from Jack Brennen sometime near July 2008 is the key to computing these
numbers.  According to my notes, his e-mail says:

"To determine if an odd number N is flimsy, take the finite set of 
residues
of 2^a (mod N). Assume that the number of 1's in the binary 
representation
of N is equal to C. To show that the number is flimsy, find a way to
construct zero (mod N) by adding up some number of residues of 2^a (mod 
N)
using less than C terms.  To show that the number is sturdy, show that 
it's
impossible to do so."

The bottom line is that this sequence, though difficult to compute, is 
well
defined.

Tony


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/