A189768 -id:A189768 - cp's OEIS frontend

A336683 Sum of 2^k for all residues k found in the Fibonacci sequence mod n.

1, 3, 7, 15, 31, 63, 127, 175, 511, 1023, 1327, 4031, 7471, 16383, 32767, 43951, 127807, 238895, 502063, 1048575, 1319215, 2719023, 7798639, 10692015, 33554431, 61209903, 134217727, 259173375, 337649967, 1073741823, 1571892655, 2880154543, 5417565487, 15638470959

Offset: 1

Michael De Vlieger, Oct 04 2020

Row n of A079002 compactified as a binary number.

			a(1) = 1 by convention.
a(2) = 3 = 2^0 + 2^1, since the Fibonacci sequence mod 2 is {0,1,1} repeated, and 0 and 1 appear in the sequence.
a(8) = 175 = 2^0 + 2^1 + 2^2 + 2^3 + 2^5 + 2^7, since the Fibonacci sequence mod 8 is {0,1,1,2,3,5,0,5,5,2,7,1} repeated, and we are missing 4 and 6, leaving the exponents of 2 as shown.
Binary equivalents of first terms:
   n    a(n)   a(n) in binary
   --------------------------
   1      1                 1
   2      3                11
   3      7               111
   4     15              1111
   5     31             11111
   6     63            111111
   7    127           1111111
   8    175          10101111
   9    511         111111111
  10   1023        1111111111
  11   1327       10100101111
  12   4031      111110111111
  13   7471     1110100101111
  14  16383    11111111111111
  15  32767   111111111111111
  16  43951  1010101110101111
  ...

Michael De Vlieger, Table of n, a(n) for n = 1..3322
Michael De Vlieger, Plot of bits of a(n) beginning with 2^0 at left for 1 <= n <= 5000.

Cf. A000045, A001175, A066853, A079002, A128924, A189768.

{1}~Join~Array[Block[{w = {0, 1}}, Do[If[SequenceCount[w, {0, 1}] == 1, AppendTo[w, Mod[Total@ w[[-2 ;; -1]], #]], Break[]], {i, 2, Infinity}]; Total[2^Union@ w]] &, 33, 2]
(* Second program: generate the first n terms using the plot in Links *)
With[{n = 34, img = ImageData@ ColorNegate@ Import["https://oeis.org/A336683/a336683.png"]}, Map[FromDigits[#, 2] &@ Drop[#, LengthWhile[#, # == 0 &]] &@ Reverse[IntegerPart[#]] &, img[[1 ;; n]]]] (* Michael De Vlieger, Oct 05 2020 *)

a(n) = Sum(2^k) for all k in row n of A189768.

a(n) = 2^(n+1) - 1 for n in A079002.

A189761 Numbers n for which the set of residues {Fibonacci(k) mod n, k=0,1,2,....} is minimal.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 11, 21, 29, 55, 76, 144, 199, 377, 521, 987, 1364, 2584, 3571, 6765, 9349, 17711, 24476, 46368, 64079, 121393, 167761, 317811, 439204, 832040, 1149851, 2178309, 3010349, 5702887, 7881196, 14930352, 20633239, 39088169, 54018521, 102334155

Offset: 1

T. D. Noe, May 10 2011

Sequence A066853 gives the number of possible residues of the Fibonacci numbers mod n. For the n in this sequence, it appears that A066853(n) < A066853(m) for all m > n. For these n, the set of residues consists of Fibonacci numbers < n and some of their negatives (see example).
Interestingly, for n > 5, this sequence alternates the even-index Fibonacci and odd-indexed Lucas numbers, A001906 and A002878. See A109794 for the sequence without 2 and 5.
The number of residues is 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 13, 15, 16, ..., which is A032766 with 2 and 5 included.

			For n=55, the residues are {0, 1, 2, 3, 5, 8, 13, 21, 34, 47, 52, 54} which can also be written as {0, 1, 2, 3, 5, 8, 13, 21, -21, -8, -3, -1}.

Index entries for linear recurrences with constant coefficients, signature (0,3,0,-1).

Cf. A001906, A002878, A032766, A066853, A109794, A189768.

Union[{2, 5}, Fibonacci[Range[2, 20, 2]], LucasL[Range[1, 20, 2]]]

Vec(x*(x^8+x^7-x^6-2*x^5-3*x^4-2*x^3+2*x+1)/((x^2-x-1)*(x^2+x-1)) + O(x^100)) \\ Colin Barker, Oct 29 2013

From Colin Barker, Oct 29 2013: (Start)
a(n) = 3*a(n-2) - a(n-4) for n > 9.
G.f.: x*(x^8 + x^7 - x^6 - 2*x^5 - 3*x^4 - 2*x^3 + 2*x + 1) / ((x^2-x-1)*(x^2+x-1)). (End)

A189767 Least number k such that the set of numbers {Fibonacci(i) mod n, i=0..k-1} contains all possible residues of Fibonacci(i) mod n.

Original entry on oeis.org

1, 2, 4, 5, 10, 10, 13, 11, 17, 22, 9, 23, 19, 37, 20, 23, 25, 19, 17, 53, 15, 25, 37, 23, 50, 61, 53, 45, 13, 58, 29, 47, 39, 25, 77, 23, 55, 17, 47, 59, 31, 37, 65, 29, 93, 37, 25, 23, 81, 148, 67, 75, 77, 53, 19, 45, 71, 37, 57, 119, 43, 29, 45, 95, 103

Offset: 1

T. D. Noe, May 10 2011

nonn

Sequence A066853 gives the number of possible residues of the sequence Fibonacci(i) mod n for i=0,1,2,.... Here we compute the smallest k required to find all A066853(n) residues in the first k terms (starting at i=0) of Fibonacci sequence (mod n). We know that k is at most A001175(n), the period of Fibonacci(i) mod n. It appears that when n is a prime in A053032, then a(n)=n-1.

			Consider n=8. The Fibonacci numbers mod 8 have period 12: 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1. The set of residues is {0, 1, 2, 3, 5, 7}. How long does it take to find all 6 residues in the sequence Fibonacci(i) mod n? The answer is 11 because 7 finally appears as Fibonacci(10) mod 8.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A000045 (Fibonacci numbers), A001175, A053032, A066853, A189768 (residues).

F:= proc(n)
 local r, k, a,ap, t, V;
ap:= 0: a:= 1; r:= 1;
V:= Array(0..n-1);
V[0]:= 1;
V[1]:= 1;
for k from 2 do
     t:= a + ap mod n;
     ap:= a;
     a:= t;
     if ap = 0 and a = 1 then return r +1 fi;
     if V[t] = 0 then
        r:=k;
        V[t]:= 1;
     fi
od:
end proc:
F(1):= 1:
seq(F(n),n=1..100); # Robert Israel, Dec 23 2015

pisano[n_] := Module[{a={1,0},a0,k=0,s}, If[n==1, 1, a0=a; While[k++; s=Mod[Total[a],n]; a[[1]]=a[[2]]; a[[2]]=s; a != a0]; k]]; Table[p=pisano[n]; f=Mod[Fibonacci[Range[0,p]],n]; u=Union[f]; k=1; While[Union[Take[f,k]] != u, k++]; k, {n,100}]

A336684 Irregular triangle in which row n lists residues k found in the sequence Lucas(i) mod n.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 6, 7, 8, 9, 0, 1, 2, 3, 4, 7, 10, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2, 3, 4, 5

Offset: 1

Michael De Vlieger, Oct 07 2020

For row n, it is sufficient to take the union of A000032(i) mod n for 0 <= i <= A106291(n - 1), since the Lucas numbers are cyclical mod n.
Row n contains the Lucas number k < n, and k such that (n + k) is a Lucas number.
Row n for n in A224482 is complete, i.e., it contains all residues k (mod n). This includes n that is a perfect power of 3.

			Row 1 contains 0 by convention.
Row 2 contains (0, 1) since the Lucas sequence contains both even and odd numbers.
Row 5 contains (1, 2, 3, 4) since the Lucas numbers mod 5 is {2,1,3,4,2,1} repeated; we are missing the residue 0.
Table begins as shown below, with residue k shown arranged in columns.
n    k (mod n)
--------------
1:   0
2:   0  1
3:   0  1  2
4:   0  1  2  3
5:      1  2  3  4
6:   0  1  2  3  4  5
7:   0  1  2  3  4  5  6
8:      1  2  3  4  5     7
9:   0  1  2  3  4  5  6  7  8
10:     1  2  3  4     6  7  8  9
11:  0  1  2  3  4        7       10
12:     1  2  3  4  5  6  7  8    10 11
13:     1  2  3  4  5  6  7  8  9 10 11 12
14:  0  1  2  3  4  5  6  7  8  9 10 11 12 13
15:     1  2  3  4        7          11       14
16:     1  2  3  4  5     7     9    11 12 13    15
...

Cf. A000032, A066981, A106291, A223487. Analogous to A189768.

{Most@ #, #} &[Range[0, 1]]~Join~Array[Block[{w = {2, 1}}, Do[If[SequenceCount[w, {2, 1}] == 1, AppendTo[w, Mod[Total@ w[[-2 ;; -1]], #]], Break[]], {i, 2, Infinity}]; Union@ w] &, 12, 3] // Flatten

A066981(n) = length of row n.
A223487(n) = n - A066981(n) = number of residues missing from row n.
A224482(n) = rows n that have complete residue coverage, i.e., A066981(n) = n and A223487(n) = 0.

A367477 a(n) is the least k such that all possible modular classes a Fibonacci number can take mod n is seen in the Fibonacci numbers Fibonacci(1)..Fibonacci(k).

Original entry on oeis.org

1, 3, 4, 6, 9, 12, 12, 10, 16, 21, 10, 22, 18, 36, 20, 22, 24, 18, 18, 52, 14, 30, 36, 22, 49, 60, 52, 44, 14, 60, 30, 46, 38, 24, 76, 22, 54, 18, 46, 58, 30, 36, 64, 30, 92, 36, 24, 22, 80, 147, 66, 74, 76, 52, 18, 44, 70, 42, 58, 118, 42, 30, 44, 94, 102, 114, 96

Offset: 1

David A. Corneth, Nov 19 2023

nonn

In verifying if k is in A367420 we only need to look from 1 to a(n) to see if there is a Fibonacci number f that has a remainder of k when dividing by 2*k.

			The remainders of Fibonacci numbers mod 4 (starting at Fibonacci(1) = 1) are 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3. The distinct values are {0, 1, 2, 3}. The least k such that the remainders of Fibonacci numbers mod 4 contain all these values is 6 as the first 6 remainders are 1, 1, 2, 3, 1, 0.

Cf. A000045, A001175, A001177, A189768, A367420.

a(n) = {if(n == 1, return(1));
	my(rems = vector(n^2), v = [1,1]);
	rems[1] = 1;
	for(i = 2, n^2,
		rems[i] = v[2];
		v = [v[2], v[1]+v[2]]%n;
		if(v == [1,1],
			break
		)
	);
	s = Set(rems);
	for(i = 1, #rems,
		s = setminus(s, Set(rems[i]));
		if(#s == 0,
			return(i)
		)
	)
}

cp's OEIS Frontend

A336683 Sum of 2^k for all residues k found in the Fibonacci sequence mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A189761 Numbers n for which the set of residues {Fibonacci(k) mod n, k=0,1,2,....} is minimal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A189767 Least number k such that the set of numbers {Fibonacci(i) mod n, i=0..k-1} contains all possible residues of Fibonacci(i) mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A336684 Irregular triangle in which row n lists residues k found in the sequence Lucas(i) mod n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A367477 a(n) is the least k such that all possible modular classes a Fibonacci number can take mod n is seen in the Fibonacci numbers Fibonacci(1)..Fibonacci(k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI