cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

A001177 Fibonacci entry points: a(n) = least k >= 1 such that n divides Fibonacci number F_k (=A000045(k)).

Original entry on oeis.org

1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, 56, 75, 36, 42, 27, 36, 10, 24, 36, 42, 58, 60, 15, 30, 24, 48, 35, 60, 68, 18, 24, 120
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

In the formula, the relation a(p^e) = p^(e-1)*a(p) is called Wall's conjecture, which has been verified for primes up to 10^14. See A060305. Primes for which this relation fails are called Wall-Sun-Sun primes. - T. D. Noe, Mar 03 2009
All solutions to F_m == 0 (mod n) are given by m == 0 (mod a(n)). For a proof see, e.g., Vajda, p. 73. [Old comment changed by Wolfdieter Lang, Jan 19 2015]
If p is a prime of the form 10n +- 1 then a(p) is a divisor of p-1. If q is a prime of the form 10n +- 3 then a(q) is a divisor of q+1. - Robert G. Wilson v, Jul 07 2007
Definition 1 in Riasat (2011) calls this k(n), or sometimes just k. Corollary 1 in the same paper, "every positive integer divides infinitely many Fibonacci numbers," demonstrates that this sequence is infinite. - Alonso del Arte, Jul 27 2013
If p is a prime then a(p) <= p+1. This is because if p is a prime then exactly one of the following Fibonacci numbers is a multiple of p: F(p-1), F(p) or F(p+1). - Dmitry Kamenetsky, Jul 23 2015
From Renault 1996:
1. a(lcm(n,m)) = lcm(a(n), a(m)).
2. if n|m then a(n)|a(m).
3. if m has prime factorization m=p1^e1 * p2^e2 * ... * pn^en then a(m) = lcm(a(p1^e1), a(p2^e2), ..., a(pn^en)). - Dmitry Kamenetsky, Jul 23 2015
a(n)=n if and only if n=5^k or n=12*5^k for some k >= 0 (see Marques 2012). - Dmitry Kamenetsky, Aug 08 2015
Every positive integer (except 2) eventually appears in this sequence. This is because every Fibonacci number bigger than 1 (except Fibonacci(6)=8 and Fibonacci(12)=144) has at least one prime factor that is not a factor of any earlier Fibonacci number (see Knott reference). Let f(n) be such a prime factor for Fibonacci(n); then a(f(n))=n. - Dmitry Kamenetsky, Aug 08 2015
We can reconstruct the Fibonacci numbers from this sequence using the formula Fibonacci(n+2) = 1 + Sum_{i: a(i) <= n} phi(i)*floor(n/a(i)), where phi(n) is Euler's totient function A000010 (see the Stroinski link). For example F(6) = 1 + phi(1)*floor(4/a(1)) + phi(2)*floor(4/a(2)) + phi(3)*floor(4/a(4)) = 1 + 1*4 + 1*1 + 2*1 = 8. - Peter Bala, Sep 10 2015
Conjecture: Sum_{d|n} phi(d)*a(d) = A232656(n). - Logan J. Kleinwaks, Oct 28 2017
a(F_m) = m for all m > 1. Indeed, let (b(j)) be defined by b(1)=b(2)=1, and b(j+2) = (b(j) + b(j+1)) mod n. Then a(n) equals the index of the first occurrence of 0 in (b(j)). Example: if n=4 then b = A079343 = 1,1,2,3,1,0,1,1,..., so a(4)=6. If n is a Fibonacci number n=F_m, then obviously a(n)=m. Note that this gives a simple proof of the fact that all integers larger than 2 occur in (a(n)). - Michel Dekking, Nov 10 2017

Examples

			a(4) = 6 because the smallest Fibonacci number that 4 divides is F(6) = 8.
a(5) = 5 because the smallest Fibonacci number that 5 divides is F(5) = 5.
a(6) = 12 because the smallest Fibonacci number that 6 divides is F(12) = 144.
From _Wolfdieter Lang_, Jan 19 2015: (Start)
a(2) = 3, hence 2 | F(m) iff m = 2*k, for k >= 0;
a(3) = 4, hence 3 | F(m) iff m = 4*k, for k >= 0;
etc. See a comment above with the Vajda reference.
(End)

References

  • A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 25.
  • B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers. Report ORNL-4261, Oak Ridge National Laboratory, Oak Ridge, Tennessee, June 1968.
  • Alfred S. Posamentier & Ingmar Lehmann, The (Fabulous) Fibonacci Numbers, Afterword by Herbert A. Hauptman, Nobel Laureate, 2. 'The Minor Modulus m(n)', Prometheus Books, NY, 2007, page 329-342.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.
  • N. N. Vorob'ev, Fibonacci numbers, Blaisdell, NY, 1961.

Links

Crossrefs

Cf. A000045, A001175, A001176, A060383, A001602. First occurrence of k is given in A131401. A233281 gives such k that a(k) is a prime.
From Antti Karttunen, Dec 21 2013: (Start)
Various derived sequences:
A047930(n) = A000045(a(n)).
A037943(n) = A000045(a(n))/n.
A217036(n) = A000045(a(n)-1) mod n.
A132632(n) = a(n^2).
A132633(n) = a(n^3).
A214528(n) = a(n!).
A215011(n) = a(A000217(n)).
A215453(n) = a(n^n).
Analogous sequence for the tribonacci numbers: A046737, for Lucas numbers: A223486, for Pell numbers: A214028.
Cf. also A000057, A106535, A120255, A120256, A175026, A213648, A214031, A214781, A214783, A230359, A233283, A233285, A233287. (End)

Programs

  • Haskell
    a001177 n = head [k | k <- [1..], a000045 k `mod` n == 0]
-- Reinhard Zumkeller, Jan 15 2014
  • Maple
    A001177 := proc(n)
        for k from 1 do
                if combinat[fibonacci](k) mod n = 0 then
                        return k;
                end if;
        end do:
end proc: # R. J. Mathar, Jul 09 2012
N:= 1000: # to get a(1) to a(N)
L:= ilcm($1..N):
count:= 0:
for n from 1 while count < N do
  fn:= igcd(L,combinat:-fibonacci(n));
  divs:= select(`<=`,numtheory:-divisors(fn),N);
  for d in divs do if not assigned(A[d]) then count:= count+1; A[d]:= n fi od:
od:
seq(A[n],n=1..N); # Robert Israel, Oct 14 2015
  • Mathematica
    fibEntry[n_] := Block[{k = 1}, While[ Mod[ Fibonacci@k, n] != 0, k++ ]; k]; Array[fibEntry, 74] (* Robert G. Wilson v, Jul 04 2007 *)
  • PARI
    a(n)=if(n<0,0,s=1;while(fibonacci(s)%n>0,s++);s) \\ Benoit Cloitre, Feb 10 2007
  • PARI
    ap(p)=my(k=p+[0, -1, 1, 1, -1][p%5+1], f=factor(k)); for(i=1, #f[, 1], for(j=1, f[i, 2], if((Mod([1, 1; 1, 0], p)^(k/f[i, 1]))[1, 2], break); k/=f[i, 1])); k
a(n)=if(n==1,return(1)); my(f=factor(n), v); v=vector(#f~, i, if(f[i,1]>1e14,ap(f[i,1]^f[i,2]), ap(f[i,1])*f[i,1]^(f[i,2]-1))); if(f[1,1]==2&&f[1,2]>1, v[1]=3<Charles R Greathouse IV, May 08 2017
  • Scheme
    (define (A001177 n) (let loop ((k 1)) (cond ((zero? (modulo (A000045 k) n)) k) (else (loop (+ k 1)))))) ;; Antti Karttunen, Dec 21 2013

Formula

A001175(n) = A001176(n) * a(n) for n >= 1.
a(n) = n if and only if n is of form 5^k or 12*5^k (proved in Marques paper), a(n) = n - 1 if and only if n is in A106535, a(n) = n + 1 if and only if n is in A000057, a(n) = n + 5 if and only if n is in 5*A000057, ... - Benoit Cloitre, Feb 10 2007
a(1) = 1, a(2) = 3, a(4) = 6 and for e > 2, a(2^e) = 3*2^(e-2); a(5^e) = 5^e; and if p is an odd prime not 5, then a(p^e) = p^max(0, e-s)*a(p) where s = valuation(A000045(a(p)), p) (Wall's conjecture states that s = 1 for all p). If (m, n) = 1 then a(m*n) = lcm(a(m), a(n)). See Posamentier & Lahmann. - Robert G. Wilson v, Jul 07 2007; corrected by Max Alekseyev, Oct 19 2007, Jun 24 2011
Apparently a(n) = A213648(n) + 1 for n >= 2. - Art DuPre, Jul 01 2012
a(n) < n^2. [Vorob'ev]. - Zak Seidov, Jan 07 2016
a(n) < n^2 - 3n + 6. - Jinyuan Wang, Oct 13 2018
a(n) <= 2n [Salle]. - Jon Maiga, Apr 25 2019

Extensions

Definition corrected by Wolfdieter Lang, Jan 19 2015

A054494 Largest Fibonacci factor of n.

Original entry on oeis.org

1, 2, 3, 2, 5, 3, 1, 8, 3, 5, 1, 3, 13, 2, 5, 8, 1, 3, 1, 5, 21, 2, 1, 8, 5, 13, 3, 2, 1, 5, 1, 8, 3, 34, 5, 3, 1, 2, 13, 8, 1, 21, 1, 2, 5, 2, 1, 8, 1, 5, 3, 13, 1, 3, 55, 8, 3, 2, 1, 5, 1, 2, 21, 8, 13, 3, 1, 34, 3, 5, 1, 8, 1, 2, 5, 2, 1, 13, 1, 8, 3, 2, 1, 21, 5, 2, 3, 8, 89, 5, 13, 2, 3, 2, 5, 8, 1, 2, 3, 5
Offset: 1

Views

Author

Henry Bottomley, Apr 04 2000

Keywords

Examples

			a(10)=5 because 1, 2 and 5 are the Fibonacci numbers which divide 10 and 5 is the largest.

Links

Crossrefs

Cf. A000045, A005086, A010056, A054495.
Sequences with similar definitions: A047930 (smallest Fibonacci multiple), A280686 (restricted to proper divisors), A280694 (equivalent for Lucas numbers).
Positions of 1's: A147956.

Programs

  • Mathematica
    With[{fibs=Fibonacci[Range[20]]},Table[Max[Select[fibs,Divisible[ n,#]&]],{n,100}]] (* Harvey P. Dale, Jul 17 2012 *)
  • PARI
    A010056(n)=my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8))
a(n)=fordiv(n,d,if(A010056(n/d), return(n/d))) \\ Charles R Greathouse IV, Nov 05 2014
  • Python
    from sympy import divisors
from sympy.ntheory.primetest import is_square
def A054494(n): return next(d for d in sorted(divisors(n,generator=True),reverse=True) if is_square(m:=5*d**2-4) or is_square(m+8)) # Chai Wah Wu, May 06 2024

Formula

a(n) = n/A054495(n).

Extensions

Corrected by Harvey P. Dale, Jul 17 2012

A037943 Smallest Fibonacci number that has n as a factor, divided by n.

Original entry on oeis.org

1, 1, 1, 2, 1, 24, 3, 1, 16, 61, 5, 12, 1, 3312, 451, 9, 2, 8, 136, 41602, 1, 37820, 2016, 6, 3001, 421, 552976, 1656, 13, 51600291864, 26840, 1449, 205, 1, 2923833, 4, 113, 68, 8149, 20801, 165, 1104, 16311831, 18910, 34400194576, 1008, 21, 3, 4609212933
Offset: 1

Views

Author

Marc LeBrun

Keywords

Examples

			Fibonacci(12) = 144 is the first that is divisible by 6, so a(6)=144/6=24.

Links

Crossrefs

Cf. A000045, A001177, A047930.

Formula

a(n) = F(A001177(n))/n.
a(n) = A047930(n)/n. - Alois P. Heinz, Jan 08 2017

A265647 Smallest k such that n divides k*(k+1)*(k+2)/6.

Original entry on oeis.org

1, 2, 7, 2, 3, 7, 5, 6, 25, 3, 9, 7, 11, 6, 8, 14, 15, 26, 17, 4, 7, 10, 21, 8, 23, 11, 79, 6, 27, 8, 29, 30, 9, 15, 5, 26, 35, 18, 25, 8, 39, 7, 41, 10, 25, 22, 45, 16, 47, 23, 16, 12, 51, 79, 9, 6, 17, 27, 57, 8, 59, 30, 26, 62, 13, 43, 65, 15, 44, 14, 69, 54, 71, 35, 25, 18, 20, 26, 77, 14, 241
Offset: 1

Views

Author

Ctibor O. Zizka, Dec 11 2015

Keywords

Comments

More generally we can ask for the smallest k such that gcd(n,f(k)) = n. This sequence has f(k) = k*(k+1)*(k+2)/6. For other examples in the OEIS, see the crossrefencess.

Links

Crossrefs

Cf. A000292, A011772, A002034, A047930, A005179, A070982, A038700, A344005, A345989.

Programs

  • Mathematica
    Table[k = 1; While[! Divisible[k (k + 1) (k + 2)/6, n], k++]; k, {n, 81}] (* Michael De Vlieger, Dec 11 2015 *)
  • PARI
    a(n)=my(k=1);while((k*(k+1)*(k+2)/6)%n>0,k++);k \\ Anders Hellström, Dec 11 2015
  • PARI
    first(n) = { my(todo = n, i = 1, res = vector(n)); while(todo > 0, d = select(x -> x <= n, divisors(binomial(i + 2, 3))); for(j = 1, #d, if(res[d[j]] == 0, res[d[j]] = i; todo-- ) ); i++ ); res } \\ David A. Corneth, Mar 22 2021

Extensions

More terms from Michael De Vlieger, Dec 11 2015

A073875 Smallest nonzero Fibonacci number divisible by n not included earlier.

Original entry on oeis.org

1, 2, 3, 8, 5, 144, 21, 2584, 46368, 610, 55, 14930352, 13, 4807526976, 6765, 1548008755920, 34, 498454011879264, 86267571272, 832040, 987, 2880067194370816120, 51680708854858323072, 160500643816367088, 75025
Offset: 1

Views

Author

Amarnath Murthy, Aug 16 2002

Keywords

Links

Crossrefs

Cf. A047930, A073876.

Programs

  • Maple
    S:= {}:
for n from 1 to 100 do
  for k from 1 do
     if member(k,S) then next fi;
     Fk:= combinat:-fibonacci(k);
     if Fk mod n = 0 then A[n]:= Fk; S:= S union {k}; break fi
  od
od:
seq(A[i],i=1..100); # Robert Israel, Jan 05 2017

Extensions

More terms from Sascha Kurz, Jan 03 2003
Name clarified by Robert Israel, Jan 05 2017
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.