Aviva Trivia

Two famous unsolved problems in number theory are 1) Goldbach’s Conjecture, which claims that every even integer > 2 is expressible as the sum of two primes; and 2) de Polignac’s conjecture, which claims that every even integer can be expressed as the difference of two consecutive primes in infinitely many ways. As these famous problems suggest, it’s interesting to observe the various ways in which numbers can be “decomposed” into prime numbers, as well as into other classes of numbers.

The purpose of this article is to investigate a somewhat unusual decomposition problem. Positive integers will be tested to see if they can be expressed as the sum of a Fibonacci number and a prime number, respectively. We will refer to these numbers as Fibonacci Prime Decompositions (FPDs).

For example, 122 is a FPD because it can be expressed thus:

122 = 13 + 109 = 21 + 101 = 55 + 67.

Note that the first number in each of the three summations is a Fibonacci number, while the second is a prime (13 is both). (A Fibonacci number is defined as: Start with 0 and 1, then get the next terms by adding the previous two Fibonacci numbers. The sequence starts: 0, 1, 1, 2, 3, 5, 8, 13, 21, …  A prime is a number whose only divisors are itself and 1.)

Let W(n) denote the number of ways an integer n can be expressed as the sum of a Fibonacci number and a prime. Our first sequence is of W(n) for n from 1 to 25.

Sequence 1:
     n: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …
W(n): 0, 1, 2, 2, 2, 2, 2, 2, 1,  3,   2,   2,   3,   2,   2,   2,  1,   2,   3,   2, …

More zeroes eventually occur in Sequence 1, which means that there are numbers not expressible as the sum of a Fibonacci number and a prime. The following sequence is of the n such that W(n)=0.
Sequence 2:
1, 35, 119, 125, 177, 208, 209, 221, 255, 287, 299, 329, 363, 416, 485, 515, 519, 535, 539, 551, 561, 567, 637, 697, 705, 718, 755, 768, 779, 784, 793, 815, 869, 875, 899, 925, 926, …

Conjecture:  There are infinitely many odd as well as even integers that cannot be expressed as the sum of a Fibonacci number and a prime.

A prime p will never occur in Sequence 2 since  p + 0  will always be at least one representation.
 
Unsolved question: Will a Fibonacci number > 1 ever be present in Sequence 2?

The following sequence is the least number k such that it has n unique representations as the sum of a Fibonacci number and a prime.

Sequence 3:

    n                 k
             1                 3
         2                 4
                      3                 8
    4                 24
    5                 74
    6                 444
    7                 1614
    8                 15684
For example, 15684 is the least FPD number having eight representations because:

    15684 = 1 + 15683
    15684 = 5 + 15679
    15684 = 13 + 15671
    15684 = 55 + 15629
    15684 = 233 + 15451
    15684 = 377 + 15307
    15684 = 1597 + 14087
    15684 = 4181 + 11503
Unsolved questions: What is the least FPD having 9 representations? Why do so many of the k values in Sequence 3 end in the digit 4?

John Forbes Nash Jr. worked with Goldbach decompositions (his short note on it can be found at his Princeton web site under the section “Goldbach Programs”) and he noticed that it’s sometimes possible to find even integers that can be expressed as a sum of two primes, such that the smaller prime cubed is greater than the larger prime. Taking inspiration from Nash’s observation, I examined FPDs such that W(n)=1, and noticed that some of the decompositions were such that the prime was less than the square root of the Fibonacci number. For example, 155 can only be expressed as 155 = 144 + 11; and notice that sqrt(144) = 12 > 11. A computer search of all n <= 105  revealed that integers with this property seemed to be rare. The following FPDs were found. Sequence 4: 146, 155, 629, 1599, 2615, 2631, 4183, 4186, 4192, 10963, 10969, 10977, 10999, 11017, 11019, 11025, 46375, 46379, 46387, 46391, 46397, 46409, 46421, 46429, 46435, 46469, 46565, 46579, 75028, 75036, 75288, ... Conjecture:  There are only finitely many FPDs with exactly one representation, such that in their decomposition the prime is less than the square root of the Fibonacci number. Another unusual yet interesting sequence is those FPDs with exactly one representation such that both numbers have the same number of decimal digits. Sequence 5: 2, 9, 65, 77, 93, 95, 123, 323, 335, 343, 377, 395, 415, 425, 437, 527, 545, 553, 583, 586, 670, 700, 715, 723, 726, 731, 749, 783, 801, 804, 833, 838, 849, 851, 901, 903, 905, 906, 923, 957, 959, 964, 965, 1003, 1078, 1081, 1113, 1115, ...  For example, in the decomposition of 1081 the prime and Fibonacci number both have three digits: 1081 = 144 + 937. Unsolved question: Is Sequence 5 infinite?