[seqfan] Re: n = Product derived from binary representation of n
Hagen von EItzen
math at von-eitzen.de
Wed Jun 10 20:31:02 CEST 2009
Jack Brennen wrote:
> No others less than 2^32 ...
>
>
I raise: no others less than 2^64.
One can speed up things a lot by investigating the bits recursively from
most to least significant:
If bits at position k+1, k+2, ... are known and determine that a <= n
<= b and c <= prod_{i>k} i^b(i,n) <= d,
then recursion can stop if e.g. c>b or d<a or floor(b/c)<ceil(a/c). If
on the other hand a=b=c=d, then a solution is found.
Otherwise try both bits, which means replacing (k,a,b,c,d) with
(k-1,a,(a+b-1)/2,c,d/k) and (k-1,(a+b+1)/2,b,k*c,d).
I started with k=64, a=0, b=2^64-1, c=1, d=64!.
Hagen
> Hans Havermann wrote:
> >/ Leroy Quet:
> />/
> />>/ Example: 12 in binary is 1100. And 12 = 4^1 * 3^1 * 2^0 * 1^0.
> />>/ The sequence of such n's begins: 1,2,6,12.
> />>/ Does this sequence continue?
> />/
> />/ If I understand this correctly, the next term is 576000
> />/ (10001100101000000000 in binary) = 20*16*15*12*10.
> />/
> />/
> />/ _______________________________________________
> />/
> />/ Seqfan Mailing list - http://list.seqfan.eu/
> />/
> />/
> /
More information about the SeqFan
mailing list