A079002 Numbers n such that the Fibonacci residues F(k) mod n form the complete set (0,1,2,...,n-1).
1, 2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35, 45, 50, 70, 75, 81, 100, 125, 135, 150, 175, 225, 243, 250, 350, 375, 405, 500, 625, 675, 729, 750, 875, 1125, 1215, 1250, 1750, 1875, 2025, 2187, 2500, 3125, 3375, 3645, 3750, 4375, 5625, 6075, 6250, 6561
Offset: 1
Keywords
Examples
Fibonacci numbers (A000045) are 0,1,1,2,3,5,8,... and their residues mod 5 are 0,1,1,2,3,0,3,3,4,...; i.e., all possible remainders mod 5 occur in the Fibonacci sequence mod 5, so 5 is in the sequence. This is not true for n=8, so 8 is not in the sequence.
References
- R. L. Graham, D. E. Knuth and O. Patashnick, "Concrete Mathematics", second edition, Addison Wesley, 1994, ex. 6.85, p. 318, p. 562.
Links
- T. D. Noe, Table of n, a(n) for n = 1..1000
- B. Avila and Y. Chen, On moduli for which the Lucas numbers contain a complete residue system, Fibonacci Quarterly, 51 (2013), 151-152.
- S. A. Burr, On moduli for which the Fibonacci numbers contain a complete system of residues, Fibonacci Quarterly, 9 (1971), 497-504.
- Cheng Lien Lang and Mong Lung Lang, Fibonacci system and residue completeness, arXiv:1304.2892 [math.NT], 2013.
Programs
-
Mathematica
Select[Range[10^4], MatchQ[FactorInteger[#], {{1, 1}}|{{2, 1}}|{{2, 2}}| {{3, }}|{{2, 1}, {3, 1}}|{{7, 1}}|{{2, 1}, {7, 1}}|{{5, }}|{{2, 1}, {5, }}|{{2, 2}, {5, }}|{{3, }, {5, }}|{{2, 1}, {3, 1}, {5, }}|{{5, }, {7, 1}}|{{2, 1}, {5, }, {7, 1}}]&] (* _Jean-François Alcover, Sep 01 2018 *) -
PARI
is(n)=n/=5^valuation(n,5); n==3^valuation(n,3) || setsearch([2,4,6,7,14],n) \\ Charles R Greathouse IV, Apr 23 2013
Formula
Consists of the integers of the forms 5^k, 2*5^k, 4*5^k, 3^j*5^k, 6*5^k, 7*5^k and 14*5^k [see Concrete Mathematics].
Extensions
Corrected by Ron Knott, Jan 05 2005
Entry revised by N. J. A. Sloane, Nov 28 2006, following a suggestion from Martin Fuller