## The Euler Phibonacci Sequence

A Problem Proposal with Software

The famous Fibonacci sequence F(n), where n is a natural number, has terms 1, 1, 2, 3, 5, 8, 13, 21,.... and is defined by F(1) = 1, F(2) = 1, and the recursion F(n) = F(n - 1) + F(n - 2) (n > 2). The ratio of consecutive terms of this sequence tends to a limit equal to phi, the golden ratio equal to 1.61803....

However, I shall focus on a different but no less important phi, the Euler phi-function, which I shall refer to as PHI to distinguish it from the golden ratio. You may recall that PHI(n) is defined as the number of natural numbers less than n and relatively prime to n. In number theory texts, it is shown that if n has prime factorization into distinct primes n = p1a....pkr, then PHI(n) = p1a-1(p1 - 1)....pkr-1(pk - 1)

I define the Euler Phibonacci sequence G(n) by G(n) = PHI(F(n)), the composition of F with PHI. (I am aware that "Phibonacci" has been used elsewhere to refer to other sequences, hence the "Euler". However, I shall refer from now on to the sequence as simply the Phibonacci sequence.) The first few terms of this sequence are

1 1 1 2 4 4 12 12 16 40 88 48 232 336

(Note: This appears as sequence A065449 in the Online Encyclopedia of Integer Sequences by N. J. A. Sloane.) I shall use this web page to post problems and observations on the Phibonacci sequence. Please check back for updates. I also plan to include a Java applet that lists terms of the sequence. If you would like to communicate any solutions or comments, then please contact me at the email address below.

Problems

1. Find a closed-form expression for G(n). (There exists such an expression for F(n).)
2. Does some expression involving successive terms of G(n) tend to a limit (as does F(n))?
3. Is G(n) / 2 prime for infinitely many n? Characterize these indices n.

Alternatively, the dual Euler Phibonacci sequence G'(n) = F(PHI(n)) can be considered. The first few terms of this sequence are

1 1 1 1 3 1 8 3 8 3 55 3 144 8 21 21....

(Note: This appears as sequence A065451 in the Online Encyclopedia of Integer Sequences.) One can also ask the above questions for this sequence.

On Fibonacci Products: two related sequences

Consider the sequence of numbers that are not expressible as products of Fibonacci numbers. Some terms are:

7, 11, 14, 17, 19, 22, 23, 28, 29, 31, 33, 35, 37, 38, 41, 43, 44, 46, 47, 49, 51, 53, 55, 56, 57,
58, 59, 61, 62, 63, 66, 67, 69, 71, 73, 74, 76, 77, 79, 82, 83, 85, 86, 87, 88, 91, 92, 93, 94, 95,
97, 98, 99, 101, 102, 103, 105, 106, 107, 109

(Note: Sequence A065105 in the Online Encyclopedia of Integer Sequences.) As an example, 63 = 32 x 7 is not expressible as a product of Fibonacci numbers since 7 is not. I conjecture that a(n + 1) - a(n) <= 5 for all n; also, that a(n + 1) - a(n) <= 3 for n >= 8.

Dually, consider the sequence of numbers expressible as products of Fibonacci numbers. The first few terms are:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15, 16, 18, 20, 21, 24, 25, 26, 27, 30, 32, 34, 36, 40, 42, 45, 48, 50, 52, 54, 55

(Note: Sequence A065108 in the Online Encyclopedia of Integer Sequences.) The latter conjecture is equivalent to the assertion that this sequence does not contain 5 consecutive numbers, and that for numbers >= 26, no 3 consecutive numbers.

Joseph L. Pe
iDEN System Engineering Tools and Statistics
Motorola Center
Schaumburg, IL

email:josephpe@excite.com

Document created on 18 November 2001 by J. L. Pe. Last updated on 22 November 2001

You are visitor number 