# What is the next term in the sequence?

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.

• It is having all digits from 0-9 so it is not binary or octo. Not having a-f so not hex. It is decimal only (most probably). Starting with 4 zeros and count of digits multiple of 8 indicates grouping of 4/8. Tried to treat 3-9 as not part of sequence... did not see any pattern :( Any clue at this point if possible... – Ashutosh Nigam Mar 22 '15 at 6:18
• I will run the program and generate some more terms – Paul Richards Mar 22 '15 at 10:15
• So all data is coming from one function and last term is 18, whereas all other terms are single digit? I hope you are not using some random number generator with a seed you only know. – Ashutosh Nigam Mar 22 '15 at 14:27
• No there are other terms that are double digits too. I will post a clue later. – Paul Richards Mar 22 '15 at 19:12

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.

• I thought the same thing, until i noticed the value for 40 (and hastily deleted my answer)! – Uri Granta Mar 21 '15 at 22:19

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.

• So downvoted. Have I made some sort of faux-pas? Did I need a better explanation of the solution? – Paul Richards Mar 26 '15 at 9:39
• Great solution! – xnor Mar 28 '15 at 6:38