A001644 -id:A001644 - cp's OEIS frontend

A093305 Number of binary necklaces of length n with no subsequence 000.

1, 2, 3, 4, 5, 9, 11, 19, 29, 48, 75, 132, 213, 369, 627, 1083, 1857, 3244, 5619, 9844, 17205, 30229, 53115, 93701, 165313, 292464, 517831, 918578, 1630933, 2900109, 5161443, 9197251, 16402841, 29283026, 52319379, 93558968, 167427845, 299846737, 537358107, 963651447, 1729192433

Offset: 1

Philippe Deléham, Apr 24 2004

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500.

Michael De Vlieger, Table of n, a(n) for n = 1..500
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2.
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 57.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Row 3 of A322057.

Cf. A000358, A001644, A280218, A280303.

Table[1/n * Sum[EulerPhi[n/d] (d Sum[Sum[Binomial[j, d - 3 k + 2 j] Binomial[k, j], {j, d - 3 k, k}]/k, {k, d}]), {d, Divisors@ n}], {n, 41}] (* Michael De Vlieger, Dec 28 2016, after Vladimir Joseph Stephan Orlovsky at A001644 *)

N=66;  x='x+O('x^N);
B(x)=x*(1+x+x^2);
A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));
Vec(A)
/* Joerg Arndt, Aug 06 2012 */

a(n) = (1/n) * Sum_{d divides n} totient(n/d)*A001644(d).
G.f.: Sum_{k>=1} phi(k)/k * log( 1/(1-B(x^k)) ) where B(x) = x*(1+x+x^2). - Joerg Arndt, Aug 06 2012
a(n) ~ d^n / n, where d = (19 + 3*sqrt(33))^(1/3)/3 + 4/(3*(19 + 3*sqrt(33))^(1/3)) + 1/3 = A058265 = 1.8392867552141611325518... - Vaclav Kotesovec, Jul 13 2019

A106282 Primes p such that the polynomial x^3-x^2-x-1 mod p has no zeros; i.e., the polynomial is irreducible over the integers mod p.

Original entry on oeis.org

3, 5, 23, 31, 37, 59, 67, 71, 89, 97, 113, 137, 157, 179, 181, 191, 223, 229, 251, 313, 317, 331, 353, 367, 379, 383, 389, 433, 443, 449, 463, 467, 487, 509, 521, 577, 619, 631, 641, 643, 647, 653, 661, 691, 709, 719, 727, 751, 797, 823, 829, 839, 859, 881

Offset: 1

T. D. Noe, May 02 2005

nonn

This polynomial is the characteristic polynomial of the Fibonacci and Lucas 3-step sequences, A000073 and A001644.

Primes of the form 3x^2+2xy+4y^2 with x and y in Z. - T. D. Noe, May 08 2005

Vincenzo Librandi, Table of n, a(n) for n = 1..300
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number

Primes in A028952.
Cf. A106276 (number of distinct zeros of x^3-x^2-x-1 mod prime(n)), A106294, A106302 (period of Lucas and Fibonacci 3-step sequence mod prime(n)), A003631 (primes p such that x^2-x-1 is irreducible mod p).
For a list of sequences giving numbers and/or primes represented by binary quadratic forms, see the "Binary Quadratic Forms and OEIS" link.

t=Table[p=Prime[n]; cnt=0; Do[If[Mod[x^3-x^2-x-1, p]==0, cnt++ ], {x, 0, p-1}]; cnt, {n, 200}];Prime[Flatten[Position[t, 0]]]

forprime(p=2,1000,if(#polrootsmod(x^3-x^2-x-1,p)==0,print1(p,", ")));
/* Joerg Arndt, Jul 19 2012 */

A125127 Array L(k,n) read by antidiagonals: k-step Lucas numbers.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 3, 4, 1, 1, 3, 7, 7, 1, 1, 3, 7, 11, 11, 1, 1, 3, 7, 15, 21, 18, 1, 1, 3, 7, 15, 26, 39, 29, 1, 1, 3, 7, 15, 31, 51, 71, 47, 1, 1, 3, 7, 15, 31, 57, 99, 131, 76, 1, 1, 3, 7, 15, 31, 63, 113, 191, 241, 123, 1

Offset: 1

Jonathan Vos Post, Nov 21 2006

			Table begins:
1 | 1  1  1   1   1   1    1    1    1    1
2 | 1  3  4   7  11  18   29   47   76  123
3 | 1  3  7  11  21  39   71  131  241  443
4 | 1  3  7  15  26  51   99  191  367  708
5 | 1  3  7  15  31  57  113  223  439  863
6 | 1  3  7  15  31  63  120  239  475  943
7 | 1  3  7  15  31  63  127  247  493  983
8 | 1  3  7  15  31  63  127  255  502 1003
9 | 1  3  7  15  31  63  127  255  511 1013

Freddy Barrera, Table of n, a(n) for n = 1..5050
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Eric Weisstein's World of Mathematics, Lucas n-Step Number

n-step Lucas number analog of A092921 Array F(k, n) read by antidiagonals: k-generalized Fibonacci numbers (and see related A048887, A048888). L(1, n) = "1-step Lucas numbers" = A000012. L(2, n) = 2-step Lucas numbers = A000204. L(3, n) = 3-step Lucas numbers = A001644. L(4, n) = 4-step Lucas numbers = A001648 Tetranacci numbers A073817 without the leading term 4. L(5, n) = 5-step Lucas numbers = A074048 Pentanacci numbers with initial conditions a(0)=5, a(1)=1, a(2)=3, a(3)=7, a(4)=15. L(6, n) = 6-step Lucas numbers = A074584 Esanacci ("6-anacci") numbers. L(7, n) = 7-step Lucas numbers = A104621 Heptanacci-Lucas numbers. L(8, n) = 8-step Lucas numbers = A105754. L(9, n) = 9-step Lucas numbers = A105755. See A000295, A125129 for comments on partial sums of diagonals.

Cf. A000012, A000032, A000204, A001644, A001648, A048887, A048888, A074048, A074584, A092921, A104621, A105754, A105755, A125129.

def L(k, n):
    if n < 0:
        return -1
    a = [-1]*(k-1) + [k] # [-1, -1, ..., -1, k]
    for i in range(1, n+1):
        a[:] = a[1:] + [sum(a)]
    return a[-1]
[L(k, n) for d in (1..12) for k, n in zip((d..1, step=-1), (1..d))] # Freddy Barrera, Jan 10 2019

L(k,n) = L(k,n-1) + L(k,n-2) + ... + L(k,n-k); L(k,n) = -1 for n < 0, and L(k,0) = k.

G.f. for row k: x*(dB(k,x)/dx)/(1-B(k,x)), where B(k,x) = x + x^2 + ... + x^k. - Petros Hadjicostas, Jan 24 2019

Corrected by Freddy Barrera, Jan 10 2019

A106279 Primes p such that the polynomial x^3-x^2-x-1 mod p has 3 distinct zeros.

Original entry on oeis.org

47, 53, 103, 163, 199, 257, 269, 311, 397, 401, 419, 421, 499, 587, 599, 617, 683, 757, 773, 863, 883, 907, 911, 929, 991, 1021, 1087, 1109, 1123, 1181, 1237, 1291, 1307, 1367, 1433, 1439, 1543, 1567, 1571, 1609, 1621, 1697, 1699, 1753, 1873, 1907, 2003

Offset: 1

T. D. Noe, May 02 2005

nonn

This polynomial is the characteristic polynomial of the Fibonacci and Lucas 3-step sequences, A000073 and A001644. The periods of the sequences A000073(k) mod p and A001644(k) mod p have length less than p. For a given p, let the zeros be a, b and c. Then A001644(k) mod p = (a^k+b^k+c^k) mod p. This sequence is the same as A033209 except for the initial term.

Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A106276 (number of distinct zeros of x^3-x^2-x-1 mod prime(n)), A106294, A106302 (periods of the Fibonacci and Lucas 3-step sequences mod prime(n)).

t=Table[p=Prime[n]; cnt=0; Do[If[Mod[x^3-x^2-x-1, p]==0, cnt++ ], {x, 0, p-1}]; cnt, {n, 500}];Prime[Flatten[Position[t, 3]]]

A104622 Indices of prime values of heptanacci-Lucas numbers A104621.

Original entry on oeis.org

0, 2, 3, 5, 7, 10, 17, 24, 25, 26, 28, 38, 40, 49, 62, 79, 89, 114, 140, 145, 182, 248, 353, 437, 654, 702, 784, 921, 931, 986, 1206, 2136, 2137, 3351, 5411, 13264, 13757, 16348, 27087, 27160

Offset: 1

Jonathan Vos Post, Mar 17 2005

The 7th-order linear recurrence A104622 (heptanacci-Lucas numbers) is a generalization of the Lucas sequence A000032. T. D. Noe and I have noted that the heptanacci-Lucas numbers have many more primes than the corresponding heptanacci (see A104414) which he found has only the first 3 primes that I identified through the first 5000 values, whereas these heptanacci-Lucas numbers have 17 primes among the first 100 values. For semiprimes in heptanacci-Lucas numbers, see A104623.

			A104621(0) = 7,
A104621(2) = 3,
A104621(3) = 7,
A104621(5) = 31,
A104621(7) = 127,
A104621(10) = 983,
A104621(17) = 122401,
A104621(24) = 15231991.

Mario Catalani, Polymatrix and Generalized Polynacci Numbers, arXiv:math.CO/0210201 v1, Oct 14 2002
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4

Cf. A000032, A001644, A073817, A074048, A074584, A104414, A104576, A104577, A104621, A104623.

a[0] = 7; a[1] = 1; a[2] = 3; a[3] = 7; a[4] = 15; a[5] = 31; a[6] = 63; a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4] + a[n - 5] + a[n - 6] + a[n - 7]; Do[ If[ PrimeQ[ a[n]], Print[n]], {n, 5000}] (* Robert G. Wilson v, Mar 17 2005 *)
Flatten[Position[LinearRecurrence[{1,1,1,1,1,1,1},{7,1,3,7,15,31,63},28000],?PrimeQ]]-1 (* _Harvey P. Dale, Jan 02 2016 *)

Prime values of the heptanacci-Lucas numbers, which are defined by: a(0) = 7, a(1) = 1, a(2) = 3, a(3) = 7, a(4) = 15, a(5) = 31, a(6) = 63, for n > 6: a(n) = a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-7).

More terms from T. D. Noe and Robert G. Wilson v, Mar 17 2005

A106276 Number of distinct zeros of x^3-x^2-x-1 mod prime(n).

Original entry on oeis.org

1, 0, 0, 1, 2, 1, 1, 1, 0, 1, 0, 0, 1, 1, 3, 3, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 3, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 3, 1, 1, 0, 0, 0, 1, 1, 3, 1, 0, 1, 0, 1, 1, 1, 0, 3, 1, 3, 1, 1, 1, 1, 1, 1, 3, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 3, 3, 1, 3, 3, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 3, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1

Offset: 1

T. D. Noe, May 02 2005

nonn

This polynomial is the characteristic polynomial of the Fibonacci and Lucas 3-step recursions, A000073 and A001644. Similar polynomials are treated in Serre's paper. The discriminant of the polynomial is -44 = -4*11. The primes p yielding 3 distinct zeros, A106279, correspond to the periods of the sequences A000073(k) mod p and A001644(k) mod p having length less than p. The Lucas 3-step sequence mod p has two additional primes p for which the period is less than p: 2 and 11, which are factors of the discriminant -44. For p=11, the Fibonacci 3-step sequence mod p has a period of p(p-1).

J.-P. Serre, On a theorem of Jordan, Bull. Amer. Math. Soc., 40 (No. 4, 2003), 429-440, see p. 433.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A106273 (discriminant of the polynomial x^n-x^(n-1)-...-x-1), A106293 (period of the Lucas 3-step sequences mod prime(n)), A106282 (prime moduli for which the polynomial is irreducible).

Table[p=Prime[n]; cnt=0; Do[If[Mod[x^3-x^2-x-1, p]==0, cnt++ ], {x, 0, p-1}]; cnt, {n, 150}]

A214826 a(n) = a(n-1) + a(n-2) + a(n-3), with a(0) = 1, a(1) = a(2) = 4.

Original entry on oeis.org

1, 4, 4, 9, 17, 30, 56, 103, 189, 348, 640, 1177, 2165, 3982, 7324, 13471, 24777, 45572, 83820, 154169, 283561, 521550, 959280, 1764391, 3245221, 5968892, 10978504, 20192617, 37140013, 68311134, 125643764, 231094911, 425049809

Offset: 0

Abel Amene, Jul 29 2012

See Comments in A214727.

Robert Price, Table of n, a(n) for n = 0..1000
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Cf. A000213, A000288, A000322, A000383, A060455, A136175, A141036, A141523, A214825-A214831.

a:=[1,4,4];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # G. C. Greubel, Apr 23 2019

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1+3*x-x^2)/(1-x-x^2-x^3) )); // G. C. Greubel, Apr 23 2019

LinearRecurrence[{1,1,1},{1,4,4},33] (* Ray Chandler, Dec 08 2013 *)

my(x='x+O('x^40)); Vec((1+3*x-x^2)/(1-x-x^2-x^3)) \\ G. C. Greubel, Apr 23 2019

((1+3*x-x^2)/(1-x-x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Apr 23 2019

G.f.: (1+3*x-x^2)/(1-x-x^2-x^3).

a(n) = K(n) - 2*T(n+1) + 5*T(n), where K(n) = A001644(n) and T(n) = A000073(n+1). - G. C. Greubel, Apr 23 2019

A306357 Number of nonempty subsets of {1, ..., n} containing no three cyclically successive elements.

Original entry on oeis.org

0, 1, 3, 6, 10, 20, 38, 70, 130, 240, 442, 814, 1498, 2756, 5070, 9326, 17154, 31552, 58034, 106742, 196330, 361108, 664182, 1221622, 2246914, 4132720, 7601258, 13980894, 25714874, 47297028, 86992798, 160004702, 294294530, 541292032, 995591266, 1831177830

Offset: 0

Gus Wiseman, Feb 10 2019

nonn

Cyclically successive means 1 is a successor of n.

Set partitions using these subsets are counted by A323949.

			The a(1) = 1 through a(5) = 20 stable subsets:
  {1}  {1}    {1}    {1}    {1}
       {2}    {2}    {2}    {2}
       {1,2}  {3}    {3}    {3}
              {1,2}  {4}    {4}
              {1,3}  {1,2}  {5}
              {2,3}  {1,3}  {1,2}
                     {1,4}  {1,3}
                     {2,3}  {1,4}
                     {2,4}  {1,5}
                     {3,4}  {2,3}
                            {2,4}
                            {2,5}
                            {3,4}
                            {3,5}
                            {4,5}
                            {1,2,4}
                            {1,3,4}
                            {1,3,5}
                            {2,3,5}
                            {2,4,5}

Cf. A000126, A000296, A001610, A001644, A169985, A306357, A323949, A323952, A323955.

stabsubs[g_]:=Select[Rest[Subsets[Union@@g]],Select[g,Function[ed,UnsameQ@@ed&&Complement[ed,#]=={}]]=={}&];
Table[Length[stabsubs[Partition[Range[n],3,1,1]]],{n,15}]

For n >= 3 we have a(n) = A001644(n) - 1.
From Chai Wah Wu, Jan 06 2020: (Start)
a(n) = 2*a(n-1) - a(n-4) for n > 6.
G.f.: x*(x^5 + x^4 - 2*x^3 + x + 1)/(x^4 - 2*x + 1). (End)

A324015 Number of nonempty subsets of {1, ..., n} containing no two cyclically successive elements.

Original entry on oeis.org

0, 1, 2, 3, 6, 10, 17, 28, 46, 75, 122, 198, 321, 520, 842, 1363, 2206, 3570, 5777, 9348, 15126, 24475, 39602, 64078, 103681, 167760, 271442, 439203, 710646, 1149850, 1860497, 3010348, 4870846, 7881195, 12752042, 20633238, 33385281, 54018520, 87403802

Offset: 0

Gus Wiseman, Feb 12 2019

nonn

Cyclically successive means 1 succeeds n.

After a(1) = 1, same as A001610 shifted once to the right. Also, a(n) = A169985(n) - 1.

			The a(6) = 17 stable subsets:
  {1}, {2}, {3}, {4}, {5}, {6},
  {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6},
  {1,3,5}, {2,4,6}.

Cf. A000045, A000126, A000296, A001610, A001644, A169985, A306357, A324014.

stabsubs[g_]:=Select[Rest[Subsets[Union@@g]],Select[g,Function[ed,UnsameQ@@ed&&Complement[ed,#]=={}]]=={}&];
Table[Length[stabsubs[Partition[Range[n],2,1,1]]],{n,0,10}]

For n <= 3, a(n) = n. Otherwise, a(n) = a(n - 1) + a(n - 2) + 1.

A004306 Rook polynomials.

Original entry on oeis.org

1, 1, 2, 6, 24, 44, 80, 144, 264, 484, 888, 1632, 3000, 5516, 10144, 18656, 34312, 63108, 116072, 213488, 392664, 722220, 1328368, 2443248, 4493832, 8265444, 15202520, 27961792, 51429752, 94594060, 173985600, 320009408, 588589064, 1082584068, 1991182536

Offset: 0

N. J. A. Sloane

a(n) is the number of perfect matchings in the circulant graph with 2*n vertices with jumps 1 and 3. - Robert Israel, Jan 24 2019

D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..400
N. Metropolis, M. L. Stein, and P. R. Stein, Permanents of cyclic (0,1) matrices, Journal of Combinatorial Theory, Volume 7, Issue 4, December 1969, Pages 291-321.
Earl Glen Whitehead, Jr., Four-discordant permutations, J. Austral. Math. Soc. Ser. A 28 (1979), no. 3, 369-377.
Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Cf. A000803. 4th column of A008305.

Equals 2 * (A001644(n) + 1), n>3.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x+ 2*x^3+13*x^4-3*x^5-6*x^6-10*x^7)/(1-2*x+x^4) )); // G. C. Greubel, Apr 22 2019

Join[{1,1,2,6},LinearRecurrence[{2,0,0,-1},{24,44,80,144},40]] (* or *) CoefficientList[ Series[ (1-x+2x^3+13x^4- 3x^5- 6x^6- 10x^7)/ (1-2x+ x^4),{x,0,40}],x] (* Harvey P. Dale, Dec 13 2011 *)

my(x='x+O('x^40)); Vec((1-x+2*x^3+13*x^4-3*x^5-6*x^6-10*x^7)/(1 -2*x+x^4)) \\ G. C. Greubel, Apr 22 2019

((1-x+2*x^3+13*x^4-3*x^5-6*x^6-10*x^7)/(1-2*x+x^4)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Apr 22 2019

G.f.: (1 - x + 2*x^3 + 13*x^4 - 3*x^5 - 6*x^6 - 10*x^7)/(1 - 2*x + x^4).

a(n) = 2*a(n-1) - a(n-4); a(0)=1, a(1)=1, a(2)=2, a(3)=6, a(4)=24, a(5)=44, a(6)=80, a(7)=144. - Harvey P. Dale, Dec 13 2011

cp's OEIS Frontend

A093305 Number of binary necklaces of length n with no subsequence 000.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A106282 Primes p such that the polynomial x^3-x^2-x-1 mod p has no zeros; i.e., the polynomial is irreducible over the integers mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A125127 Array L(k,n) read by antidiagonals: k-step Lucas numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Formula

Extensions

A106279 Primes p such that the polynomial x^3-x^2-x-1 mod p has 3 distinct zeros.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A104622 Indices of prime values of heptanacci-Lucas numbers A104621.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A106276 Number of distinct zeros of x^3-x^2-x-1 mod prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A214826 a(n) = a(n-1) + a(n-2) + a(n-3), with a(0) = 1, a(1) = a(2) = 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A306357 Number of nonempty subsets of {1, ..., n} containing no three cyclically successive elements.

Views

Author