Sequences A005245, A061373

[Ed Pegg Jr]

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.