[seqfan] Re: Sturdy and flimsy numbers.
franktaw at netscape.net
franktaw at netscape.net
Mon Dec 21 03:18:32 CET 2009
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/
More information about the SeqFan
mailing list