login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A286105 a(1) = 0; for n > 1, a(n) = 1 + max(a(A285734(n)), a(A285735(n))). 4
0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 6, 6, 7, 6, 7, 6, 7, 7, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 7, 8, 8, 7, 7, 7, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 7, 8, 8, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 (list; graph; refs; listen; history; text; internal format)
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

a(1) = 0 and for n > 1, a(n) = 1 + max(a(A285734(n)), a(A285735(n))).

a(1) = 1 and for n > 1, a(n) = 1 + a(A286107(n)).

Other identities. For all n >= 1:

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

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)

(definec (A286105 n) (if (= 1 n) 0 (+ 1 (max (A286105 (A285734 n)) (A286105 (A285735 n))))))

(definec (A286105 n) (if (= 1 n) 0 (+ 1 (A286105 (A286107 n)))))

(Python)

from sympy.ntheory.factor_ import core

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

def a285734(n):

    if n==1: return 0

    j=int(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 xrange(1, 121)] # Indranil Ghosh, May 02 2017

CROSSREFS

Cf. A005117, A285734, A285735, A286103, A286104, A286106, A286107.

Sequence in context: A274102 A261100 A130249 * A061071 A122258 A263089

Adjacent sequences:  A286102 A286103 A286104 * A286106 A286107 A286108

KEYWORD

nonn

AUTHOR

Antti Karttunen, May 02 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 07:30 EDT 2019. Contains 323478 sequences. (Running on oeis4.)