[seqfan] Re: n = Product derived from binary representation of n

[Hagen von EItzen]

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/
> />/ 
> />/ 
> /