What is the next term in the sequence?

Question

The first term is f(0), the last term is f(2000):

0,0,0,0,1,0,1,0,2,1,1,0,2,0,1,1,3,0,2,0,2,1,1,0,3,1,1,2,2,0,2,0,4,1,1,1,3,0,1,1,5,0,2,0,2,2,1,0,4,1,2,1,2,0,3,1,5,1,1,0,3,0,1,2,6,1,2,0,2,1,2,0,4,0,1,2,2,1,2,0,4,3,1,0,5,1,1,1,5,0,3,1,2,1,1,1,6,0,2,2,3,0,2,0,5,2,1,0,4,0,2,1,4,0,2,1,2,2,1,1,4,1,1,1,2,2,3,0,7,1,2,0,5,1,1,3,5,0,2,0,3,1,1,1,6,1,1,2,2,0,3,0,5,2,2,1,5,0,1,1,8,1,4,0,2,2,1,0,4,1,2,2,2,0,2,2,9,1,1,0,4,0,2,1,5,1,2,1,2,3,2,0,7,0,1,2,3,0,5,0,4,1,1,1,5,1,1,2,9,1,3,0,2,1,1,1,6,1,1,1,5,1,2,0,8,3,1,0,5,0,2,2,5,0,5,1,2,1,2,0,8,0,2,4,2,2,2,1,5,1,3,0,4,1,1,2,10,0,2,1,5,2,1,0,4,1,2,1,2,0,4,0,9,2,1,2,5,0,1,2,4,0,2,0,2,2,2,1,7,1,2,1,2,0,3,1,5,5,1,1,4,1,1,1,9,1,5,0,3,1,2,0,9,0,1,3,2,0,2,1,7,1,2,1,6,2,1,1,5,1,3,0,2,2,1,1,8,0,2,1,5,1,5,2,5,2,1,0,5,0,3,5,8,0,2,1,2,2,1,0,6,1,1,2,3,1,2,0,9,2,2,1,5,0,2,3,5,1,4,0,5,1,1,0,10,2,1,2,2,0,3,1,4,1,1,1,4,0,1,2,6,0,2,1,2,4,2,1,9,0,2,1,2,1,5,1,8,1,2,0,4,0,1,2,5,2,2,1,2,2,2,0,7,0,2,2,2,1,2,0,4,3,2,0,5,1,1,1,7,0,4,1,2,1,1,2,9,0,1,5,5,0,3,0,9,2,1,0,4,1,2,1,5,1,2,2,5,2,1,0,7,1,1,2,3,1,6,0,5,1,3,0,5,1,2,3,9,1,2,0,4,1,1,0,8,1,2,2,2,0,5,1,11,5,1,1,5,1,2,1,4,0,5,0,2,3,1,1,8,1,2,2,5,1,2,1,5,1,1,2,6,0,1,1,12,1,3,0,2,2,3,1,9,1,1,2,2,0,5,1,6,2,1,0,5,1,1,4,5,0,5,0,3,1,2,2,10,0,2,1,5,1,2,1,5,3,1,0,4,1,2,1,9,0,4,2,2,1,2,0,8,0,2,2,2,2,2,0,12,2,2,1,4,0,1,2,4,0,2,0,5,5,1,1,8,3,1,2,2,1,4,0,5,1,1,1,5,2,2,2,13,0,2,0,5,2,2,0,7,1,3,2,2,0,2,1,9,2,2,0,4,0,1,2,5,2,5,1,2,1,2,1,7,0,1,4,3,0,2,1,4,1,2,0,9,1,3,1,9,1,5,0,2,3,1,1,9,1,1,1,4,0,4,1,14,2,1,1,5,0,2,2,5,1,3,2,2,1,1,0,7,1,2,1,2,2,3,0,4,6,2,1,5,0,1,3,12,1,5,0,5,2,2,0,9,1,1,2,3,1,4,0,9,1,2,1,6,0,1,2,4,0,2,1,2,5,1,1,11,0,3,1,2,0,5,2,5,2,1,1,4,1,2,5,6,1,2,0,2,1,2,1,8,1,1,2,2,0,3,1,14,2,1,1,5,2,2,1,5,0,6,0,5,1,2,1,8,1,1,3,5,0,2,0,5,3,2,0,9,0,2,1,14,2,2,1,3,5,1,0,6,1,1,1,2,2,5,2,9,1,3,1,5,0,2,5,5,0,3,0,5,2,1,0,13,1,1,2,5,1,5,1,5,2,2,3,5,0,1,1,15,0,4,0,3,2,1,0,9,1,2,4,2,1,2,1,13,2,1,1,6,1,2,2,5,1,2,0,2,2,3,0,8,1,1,2,2,1,4,0,16,1,1,1,4,2,1,2,12,0,5,2,2,1,1,2,8,0,2,1,5,0,2,1,9,4,2,0,5,1,3,1,4,0,5,1,2,2,1,1,13,1,2,2,2,1,5,0,4,2,2,0,7,1,1,3,9,0,2,1,4,2,1,0,9,1,2,2,3,1,4,0,12,1,2,1,5,0,1,5,15,2,2,1,2,2,1,1,7,0,2,1,5,0,3,2,5,2,1,0,4,0,2,2,17,2,4,1,2,3,2,0,9,0,2,5,5,1,2,0,15,1,1,1,9,2,1,1,5,0,4,0,2,4,2,1,14,1,2,1,5,0,5,0,4,2,2,1,5,0,2,3,9,1,2,2,2,1,3,1,7,1,1,2,2,2,2,0,14,3,2,0,4,0,1,2,5,0,5,1,4,1,2,0,8,2,2,5,2,0,5,1,5,2,1,1,9,0,2,1,14,1,3,0,2,4,1,2,9,0,2,2,2,1,6,1,9,1,1,1,4,1,1,2,4,1,2,1,5,1,3,0,11,0,1,3,3,1,2,1,16,5,2,0,5,1,2,1,9,1,4,0,2,2,1,2,6,1,2,2,5,0,2,2,12,2,1,0,8,1,3,1,5,0,2,1,3,3,1,1,18,0,1,1,5,1,5,1,5,2,3,1,5,0,1,6,14,0,5,1,5,2,2,0,8,3,1,1,2,0,5,0,6,2,1,2,5,0,1,2,16,1,4,1,2,2,2,1,14,0,4,2,2,1,3,1,5,1,2,0,8,1,1,1,9,2,2,1,2,5,2,1,9,1,3,3,5,0,5,0,19,2,1,0,5,1,1,3,4,0,5,0,3,1,1,2,10,0,2,1,4,0,5,0,5,5,1,0,5,2,2,2,12,1,5,1,5,1,1,0,15,0,1,4,2,2,3,0,9,1,3,2,9,1,2,2,5,1,2,1,5,2,2,1,13,1,1,1,2,1,6,1,4,2,1,1,5,1,2,2,15,0,2,1,5,3,1,0,8,1,2,1,4,0,2,3,12,4,2,1,4,0,1,1,5,1,4,1,2,1,2,1,12,1,2,5,2,1,2,0,15,1,1,1,8,1,2,2,13,0,5,1,2,2,2,1,9,1,1,2,5,2,5,0,9,3,2,0,4,0,3,5,5,0,2,2,2,1,1,0,20,1,2,2,3,2,2,0,5,5,5,0,4,0,1,2,6,1,7,0,5,1,2,2,9,1,1,2,2,1,4,0,14,1,2,2,9,1,1,2,16,0,3,0,5,4,1,0,12,0,2,2,2,0,5,2,4,1,2,0,6,1,1,2,12,2,2,1,5,1,2,0,7,1,1,2,2,1,3,2,15,3,1,0,5,2,2,1,5,1,4,0,2,2,2,1,17,1,1,4,4,1,2,0,5,2,1,2,9,0,5,2,9,0,5,1,2,2,2,0,15,1,2,1,3,1,9,0,14,1,2,0,5,2,1,4,5,1,2,0,5,2,2,0,7,1,2,2,2,1,5,1,5,5,1,2,4,0,2,2,21,0,5,1,2,2,2,0,9,0,3,2,5,0,2,2,9,3,1,0,7,0,1,1,16,3,2,0,5,2,2,1,14,1,2,2,2,0,4,1,16,1,1,1,5,2,1,5,9,1,4,1,5,2,1,1,8,0,1,2,5,1,2,0,13,5,3,0,5,0,2,1,4,1,9,2,2,2,1,1,18,1,2,3,2,1,2,1,5,1,3,1,9,0,3,2,12,0,2,0,4,6,2,1,9,2,1,1,5,0,4,1,9,1,1,3,4,1,1,2,16,0,5,0,2,3,1,1,11,2,2,1,2,0,3,1,16,2,2,1,4,0,2,2,9,1,5,0,3,2,4,1,9,0,1,4,2,1,2,0,18,1,1,1,6,1,1,2,4,1,5,2,2,2,1,2,12,0,2,1,5,1,8,0,5,3,2,0,5,0,2,2,19,1,3,1,2,1,2,1,18,0,2,1,5,2,5,1,9,5,2,0,5,2,1,3,5,1,5,1,4,1,1,0,14,2,2,5,2,1,5,0,5,2,2,1,8,1,1,1,15,1,2,1,2,5,2,0,6,1,5,1,2,1,5,2,14,1,1,2,9,0,3,4,5,1,2,0,2,2,3,0,14,0,1,4,5,0,2,0,16,3,1,1,5,2,2,2,12,0,6,1,5,1,1,1,9,1,2,2,4,0,2,1,15,2,1,0,9,1,2,3,5,0,3,1,2,5,2,1,19,1,2,1,5,3,5,1,5,1,2,0,4,0,1,5,6,1,3,1,5,1,1,1,10,1,2,2,2,0,4,0,12,5,1,2,5,1,2,1,15,1,5,1,2,2,1,1,12,1,2,5,3,0,5,2,4,1,2,0,6,1,1,1,14,1,2,0,5,3,2,1,9,0,1,3,2,0,9,0,18

Clue

The actual values of the function matter only insofar as they assign integers into groups. So concentrate on what the numbers in a group have in common.

Don't worry too much about the first two entries (for 0 and 1), they may be misleading.

Answer 1

I had thought the n'th element of the sequence (starting at 0) was one less than the number of prime factors of n, handling 0 and 1 separately, but some numbers give greater values, all of them having at least four factors. For all values not listed, the prediction is correct.

Number   Value   #Fac-1  Factorization
40       5       3       [2, 2, 2, 5]
56       5       3       [2, 2, 2, 7]
64       6       5       [2, 2, 2, 2, 2, 2]
84       5       3       [2, 2, 3, 7]
88       5       3       [2, 2, 2, 11]
96       6       5       [2, 2, 2, 2, 2, 3]
104      5       3       [2, 2, 2, 13]
128      7       6       [2, 2, 2, 2, 2, 2, 2]
132      5       3       [2, 2, 3, 11]
136      5       3       [2, 2, 2, 17]
144      6       5       [2, 2, 2, 2, 3, 3]
152      5       3       [2, 2, 2, 19]
156      5       3       [2, 2, 3, 13]
160      8       5       [2, 2, 2, 2, 2, 5]
176      9       4       [2, 2, 2, 2, 11]
184      5       3       [2, 2, 2, 23]
192      7       6       [2, 2, 2, 2, 2, 2, 3]
198      5       3       [2, 3, 3, 11]
204      5       3       [2, 2, 3, 17]

It's particularly weird that $2^k$ gives $k-1$, for $k\leq 4$, but $2^6$ gives $6$ and $2^7$ gives $7$.

k    f(2^k)
1    0
2    1
3    2
4    3
5    4
6    6
7    7

There's also the weird fact that $f(40)=5$ and $f(80)=4$, so it's not even monotonic in the divisibility partial order.

Answer 2

The solution is:

For each nonnegative integer n, create a binary tree thus. The root vertex is n. If n is a composite number, it has two child vertices. The values in these child vertices, {a, b} are chosen such that a x b = n and a is the largest integer divisor less than or equal to the square root of n. b is the smallest integer divisor greater than or equal to the square root of n. The rest of the tree is defined recursively; the child nodes of a and b are factors of those numbers, if they are composite, and so on. Thus the leaf nodes of the tree will all be prime numbers; the only exceptions to this are the trees constructed for 0 and 1, which have only one vertex. Each of the binary trees are placed into isomorphic groups, and these are numbered 0, 1, 2.. and so on. f(n) is simply the index of the group which its tree belongs to. 0, 1 and prime numbers all have only one vertex, thus these trees form the first group and the function will take the value of 0. The first composite number, 4, has a tree with 3 nodes and thus is in the next group with index 1.