OFFSET
1,3
COMMENTS
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 furthest removed from the root.
LINKS
Antti Karttunen, Table of n, a(n) for n = 1..10000
FORMULA
EXAMPLE
A285734(2) = A285735(2) = 1, thus a tree with root 2 has just two leaves 1 and 1, so the maximum distance to them is 1, thus a(2) = 1.
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 distance to a farthest leaf (1) is two edges, thus a(3) = 2.
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 maximum distance to a leaf (1) is 1 + longest distance computed for cases 2 and 3, thus a(5) = 1 + max(1,2) = 3.
The tree with root 17 looks like this:
17
|
..................../ \..................
7 10
2......../ \........5 5......../ \........5
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
1 1 2 3 2 3 2 3
1 1 1 2 1 1 1 2 1 1 1 2
1 1 1 1 1 1
We see that the longest distance to 1 from the root can be found for example at the right border of the tree, five edges in total, thus a(17) = 5.
PROG
(Scheme, with memoization-macro definec)
(Python)
from sympy.ntheory.factor_ import core
def issquarefree(n): return core(n) == n
def a285734(n):
if n==1: return 0
j=n//2
while True:
if issquarefree(j) and issquarefree(n - j): return j
else: j-=1
def a285735(n): return n - a285734(n)
def a286105(n): return 0 if n==1 else 1 + max(a286105(a285734(n)), a286105(a285735(n)))
print([a286105(n) for n in range(1, 121)]) # Indranil Ghosh, May 02 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, May 02 2017
STATUS
approved