Sequences A005245, A061373

[benoit]

Thanks for disproving this "claim". This was too simple to be true.  
Perhaps something like :

c < A005245(n)/A061373(n)<=1 for some constant c<1

could hold...

Regards
B. Cloitre


> Sequence A005245:
> Complexity of n: number of 1's required to build n using + and ×.
>
> Sequence A061373:
> "Natural" logarithm, defined inductively by
> a(1)=1, a(p)=1+a(p-1) if p is prime, and a(n×m)=a(n)+a(m) if n, m>1.
>
> Benoit Cloitre conjectured (in A005245):
> It's known that a(n)<= A061373(n) but I think
> 0 <= A061373(n)-a(n) <= 1 also holds.
>
> This turns out to be false.
> The numbers {46, 235, 649, 1081, 7849, 31669, 61993}
> require {1,2,3,4,5,6,7} less 1's in A005245  
> <http://www.research.att.com/projects/OEIS?Anum=A005245> than in  
> A061373  
> <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/ 
> eisA.cgi?Anum=A061373>.
>
> The number 235 is the first counterexample to Benoit Cloitre's  
> conjecture:
> 235 = ((1+1)×(1+1)+1)×((1+1)×((1+1)×((1+1)×((1+1)×(1+1)+1)+1)+1)+1) --  
> using 5×47 -- needs 19 1's
> 235 = (1+1)×(1+1+1)×(1+1+1)×((1+1+1)×(1+1)×(1+1)+1)
> -- using 2×3×3×13+1 -- only needs 17 1's.
>
> A Mathematica notebook with generating code for these sequence is at
> http://library.wolfram.com/infocenter/MathSource/5175/
>
> This problem has a natural extension into the complex numbers, which
> produces some interesting images.
>
> --Ed Pegg Jr.
>
>