login
a(1) = 0; for n > 1, a(n) = 1 + min(a(A285734(n)), a(A285735(n))).
3

%I #24 May 08 2021 23:06:11

%S 0,1,1,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,

%T 4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,

%U 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,5,6,6,6,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6

%N a(1) = 0; for n > 1, a(n) = 1 + min(a(A285734(n)), a(A285735(n))).

%C By invoking A285734 and A285735 recursively, any natural number n > 1 can be decomposed as a sum of successively smaller squarefree numbers, until only n instances of 1's remain. This process can be depicted as a binary tree, where 1's are leaves, and any other node n branches to the left as A285734(n) and to the right as A285735(n). This sequence gives the distance from the root of tree (n) to a leaf (1) that is nearest to the root.

%H Antti Karttunen, <a href="/A286103/b286103.txt">Table of n, a(n) for n = 1..10000</a>

%F a(1) = 0; for n > 1, a(n) = 1 + min(a(A285734(n)), a(A285735(n))).

%F a(1) = 0; for n > 1, a(n) = 1 + a(A286104(n)).

%F Other identities. For all n >= 1:

%F a(2*A005117(n)) = 1+a(A005117(n)).

%e A285734(2) = A285735(2) = 1, thus a tree with root 2 has just two leaves 1 and 1, so the minimum distance to them is 1, thus a(2) = 1.

%e A285734(3) = 1 and A285735(3) = 2, thus a tree with root 3 has one immediate leave 1 and the subtree 2 as its other branch, so the minimum distance to a leaf (1) is one edge, thus a(3) = 1.

%e A285734(5) = 2 and A285735(3) = 3, thus a tree with root 5 has the subtree 2 as its other branch, and the subtree 3 as the other branch, so the minimum distance to a leaf (1) is 1 + shortest distance computed for cases 2 and 3, thus a(5) = 1 + min(1,1) = 2.

%e The tree with root 17 looks like this:

%e 17

%e |

%e ..................../ \..................

%e 7 10

%e 2......../ \........5 5......../ \........5

%e / \ / \ / \ / \

%e / \ / \ / \ / \

%e / \ / \ / \ / \

%e 1 1 2 3 2 3 2 3

%e 1 1 1 2 1 1 1 2 1 1 1 2

%e 1 1 1 1 1 1

%e We see that the shortest distance to 1 from the root is at the left border of the tree, just three edges, thus a(17) = 3.

%o (Scheme, with memoization-macro definec)

%o (definec (A286103 n) (if (= 1 n) 0 (+ 1 (min (A286103 (A285734 n)) (A286103 (A285735 n))))))

%o (definec (A286103 n) (if (= 1 n) 0 (+ 1 (A286103 (A286104 n)))))

%o (Python)

%o from sympy.ntheory.factor_ import core

%o def issquarefree(n): return core(n) == n

%o def a285734(n):

%o if n==1: return 0

%o j=n//2

%o while True:

%o if issquarefree(j) and issquarefree(n - j): return j

%o else: j-=1

%o def a285735(n): return n - a285734(n)

%o def a286103(n): return 0 if n==1 else 1 + min(a286103(a285734(n)), a286103(a285735(n)))

%o print([a286103(n) for n in range(1, 121)]) # _Indranil Ghosh_, May 02 2017

%Y Cf. A005117, A285734, A285735, A286104, A286105, A286106.

%K nonn

%O 1,4

%A _Antti Karttunen_, May 02 2017