Finding Fibonacci and Tribonacci Seed Numbers

Today I turned 25667 days old. This number is prime but there is little of interest to be found concerning its properties in either the OEIS or NumbersAplenty, my usual resources. For a while now, the idea that every number could be considered as being part of a Fibonacci sequence has been knocking around in my head.

Today the idea came into focus when I started to look at 25667 in this light. I knew that the ratio of consecutive terms in a Fibonacci sequence approached closer and closer to the Golden Ratio as the terms got larger. I figured I'd use this property to find the previous term.$$ \frac{25667}{\frac{1+ \sqrt {5}}{2}} \approx 15863.0783892436$$Rounding to the nearest whole number gives 15863 and from there it is easy to reverse engineer the remaining terms until a point is reached where the previous term is larger than the subsequent term. This is the point at which the algorithm I developed will stop.

Here is the SageMathCell permalink to the algorithm and Figure 1 shows a screenshot of the SageMath code.

Figure 1

The sequence of Fibonacci terms is:

25667 15863 9804 6059 3745 2314 1431 883 548 335 213 122 91 31

The two seed numbers are 31 and 91. Different numbers produce different sequences, even when only differing by 1. Consider the sequences for the two previous numbers: 25666 and 25665.

25666 15862 9804 6058 3746 2312 1434 878 556 322 234 88

25665 15862 9803 6059 3744 2315 1429 886 543 343 200 143 57

Of course, changing the manner in which the immediate predecessor of the starting number is calculated can affect the sequence. Suppose instead of rounding the decimal number, we simply truncated it, discarding the decimal part and leaving only the whole number. In the examples cited, the sequence remains the same for 25667 and 25666 but there is a difference in the case of 25655.

25665 15861 9804 6057 3747 2310 1437 873 564 309 255 54

The reason is that the decimal number is 15861.8423212660, so that rounding produces 15862 whereas truncating produces 15861. I think rounding is the better way to calculate the immediate predecessor of the starting number because this gives a result that is closest to the Golden Ration when the two numbers are compared. This benefit is clearly seen when a number from the classic Fibonacci sequence is entered e.g. 6765.

6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 
(using rounding)

6765 4180 2585 1595 990 605 385 220 165 55 
(using truncation)

Now every number can be associated with two seed numbers so that the three of them form part of a Fibonacci sequence.

Of course, the idea can be extended to tribonacci numbers with a slight modification of the code. Information about the tribonacci constant can be found here. Here is a permalink to the SageMathCell code and Figure 2 shows a screenshot of the SageMath code:

Figure 2

The sequence of tribonacci terms is:

25667 13955 7587 4125 2243 1219 663 361 195 107 59 29 19 11

So every number can be associated with three tribonacci seed numbers.

Ulam Numbers

I've been encountering these numbers for a while now, ever since making use of the website NUMBERS APLENTY which categorises numbers in a wide variety of ways and one of those categories is that of the Ulam number. Yesterday for example I was 25384 days old and 25384 is an Ulam number defined by the site as:

The Ulam sequence is defined by \(U_1=1, U_2=2 \) and, for \( k>2, U_k \) is the smallest integer that can be written in exactly one way as \(U_i+U_j \) with \( i<j<k \). The members of the Ulam sequence are called Ulam numbers. 

For example, after the first 4 terms which are trivially 1, 2, 3 and 4, the value of \(U_5 \) cannot be 5, since \(5=U_1+U_4=U_2+U_3 \), but it is 6, which can be obtained only as  \( U_2+U_4\)  (not as \(U_3+U_3 \) because the terms added must be distinct).

The problem with the Online Encyclopaedia of Integer Sequences (OEIS) is that it will not flag large numbers like 25384 as Ulam numbers because the numbers in the Ulam sequence (OEIS A002858) are only listed up to 339.

1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339

There is a list of the first 10,000 Ulam numbers in the links but these numbers do not show up in a search of the OEIS. That's why sites like NUMBERS APLENTY are so useful as a supplement to the OEIS. The site always provides a link to the relevant sequence in the OEIS as well as a Mathworld and Wikipedia link.

So what's special about the Ulam numbers? To begin with they are not distributed uniformly. As the NUMBERS APLENTY website states:

Ulam numbers are not distributed uniformly, but their density has peaks at an average distance of 21.6 (see Figure 1):

A plot of the Ulam numbers up to 1082, arranged line by line in a square 108×108. 

The plot shows the peaks in their density that occur with a frequency roughly equal to 108/5=21.6.

Wikipedia claims that the Ulam numbers have a density of approximately 0.07398 or 7.4%. It also states that:

There are infinitely many Ulam numbers. For, after the first n numbers in the sequence have already been determined, it is always possible to extend the sequence by one more element: \( U_{n − 1} + U_n \) is uniquely represented as a sum of two of the first n numbers, and there may be other smaller numbers that are also uniquely represented in this way, so the next element can be chosen as the smallest of these uniquely representable numbers.

Wikipedia goes on to say that:

The idea can be generalised as (u, v)-Ulam numbers by selecting different starting values (u, v). A sequence of (u, v)-Ulam numbers is regular if the sequence of differences between consecutive numbers in the sequence is eventually periodic. When v is an odd number greater than three, the (2, v)-Ulam numbers are regular. When v is congruent to 1 (mod 4) and at least five, the (4, v)-Ulam numbers are again regular. However, the Ulam numbers themselves do not appear to be regular. 

A sequence of numbers is said to be s-additive if each number in the sequence, after the initial 2s terms of the sequence, has exactly s representations as a sum of two previous numbers. Thus, the Ulam numbers and the (u, v)-Ulam numbers are 1-additive sequences. 

If a sequence is formed by appending the largest number with a unique representation as a sum of two earlier numbers, instead of appending the smallest uniquely representable number, then the resulting sequence is the sequence of Fibonacci numbers. 

This last point about the similarity with the Fibonacci numbers is interesting. Of course the Fibonacci numbers get very big very quickly while the Ulam numbers, because the smallest sum of any two previous numbers is sought, remain relatively smaller.

 Mathworld has a table of some of the other Ulam sequences:

I was struggling to get my SAGE code to generate these sequences of terms but came across some Python 2 code (source) that does the job, although I'm struggling to understand how it works:

ulams=[ ]
ulams.append(1)
ulams.append(2)
limit=100
sums=[0 for i in range(2*limit)]
newUlam=2
sumIndex=1
while(newUlam <limit):
  for i in ulams:
if (i<newUlam):
sums[i+newUlam] += 1
while(sums[sumIndex]!=1):
sumIndex += 1
newUlam = sumIndex
sumIndex += 1
ulams.append(newUlam) for i in ulams:
print i

With the limit set to 100, the following output is produced: 1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102

The code can be easily modified to generate other sequences with different starting terms e.g. 2 and 3:

ulams=[ ]
ulams.append(2)
ulams.append(3)
limit=100
sums=[0 for i in range(2*limit)]
newUlam=3
sumIndex=1
while(newUlam <limit):
  for i in ulams:
if (i<newUlam):
sums[i+newUlam] += 1
while(sums[sumIndex]!=1):
sumIndex += 1
newUlam = sumIndex
sumIndex += 1
ulams.append(newUlam) for i in ulams:
print i

This code produces the output: 2 3 5 7 8 9 13 14 18 19 24 25 29 30 35 36 40 41 46 51 56 63 68 72 73 78 79 83 84 89 94 115

ADDENDUM: I finally developed my own code which I do understand and it works! Here are the terms below 200 in the Ulam sequence beginning 2,3:

ulam=[i for i in range(1,200)]
ulam[0], ulam[1]=2,3
k=2
while k<len(ulam):
    count=0
    for x in range(k):
        for y in range(k):
            if ulam[x] > ulam[y]:
                if ulam[x] + ulam[y] == ulam[k]:
                    count+=1
    if count!=1:
        ulam.remove(ulam[k])
        k-=1
    k+=1
print ulam  

This code produces the output: 2, 3, 5, 7, 8, 9, 13, 14, 18, 19, 24, 25, 29, 30, 35, 36, 40, 41, 46, 51, 56, 63, 68, 72, 73, 78, 79, 83, 84, 89, 94, 115, 117, 126, 153, 160, 165, 169, 170, 175, 176, 181, 186, 191

Here is a link to an interesting article that looks at patterns in these 1-additive sequences.