A189768 -id:A189768

Search: a189768 -id:a189768

Displaying 1-5 of 5 results found.

page 1

A336683

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

+10
2

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Row n of A079002 compactified as a binary number.

LINKS

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.

FORMULA

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

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

EXAMPLE

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

...

MATHEMATICA

{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 *)

CROSSREFS

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

KEYWORD

nonn,easy

AUTHOR

Michael De Vlieger, Oct 04 2020

STATUS

approved

A189761

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

+10
1

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..40.

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

FORMULA

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)

EXAMPLE

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}.

MATHEMATICA

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

PROG

(PARI) 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

CROSSREFS

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

KEYWORD

nonn,easy

AUTHOR

T. D. Noe, May 10 2011

STATUS

approved

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.

+10
1

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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.

LINKS

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

EXAMPLE

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.

MAPLE

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;

od:

end proc:

F(1):= 1:

seq(F(n), n=1..100); # Robert Israel, Dec 23 2015

MATHEMATICA

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}]

CROSSREFS

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

KEYWORD

nonn

AUTHOR

T. D. Noe, May 10 2011

STATUS

approved

A336684

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

+10
1

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..85.

FORMULA

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.

EXAMPLE

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

...

MATHEMATICA

{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

CROSSREFS

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

KEYWORD

nonn,tabf,easy

AUTHOR

Michael De Vlieger, Oct 07 2020

STATUS

approved

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).

+10
0

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..67.

EXAMPLE

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.

PROG

(PARI)

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)

)

}

CROSSREFS

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

KEYWORD

nonn

AUTHOR

David A. Corneth, Nov 19 2023

STATUS

approved

page 1

Search completed in 0.007 seconds