Reiner Martin - cp's OEIS frontend

A063377 Sophie Germain degree of n: number of iterations of n under f(k) = 2k+1 before we reach a number that is not a prime.

0, 5, 2, 0, 4, 0, 1, 0, 0, 0, 3, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0

Offset: 1

Reiner Martin, Jul 14 2001

nonn

a(n) >= 1 means that n is prime; a(n) >= 2 means that n is a Sophie Germain prime. Is the Sophie Germain degree always finite? Is it unbounded?
A339579 is an essentially identical sequence from 1981. - N. J. A. Sloane, Dec 24 2020
From Michael S. Branicky, Dec 24 2020: (Start)
All n > 5 with a(n) >= 4 satisfy n == 9 (mod 10).
Proof.  Let f^k(n) denote iterates of 2*k + 1, with f^0(n) = n.
n != 0, 2, 4, 5, 6, or 8 (mod 10), otherwise f^0(n) is not prime, and a(n) = 0.
n != 7 (mod 10) otherwise f^1(n) = 2*n + 1 == 5 (mod 10), not prime, and a(n) <= 1.
n != 3 (mod 10) otherwise f^2(n) = 4*r + 3 == 5 (mod 10), not prime, and a(n) <= 2.
n != 1 (mod 10) otherwise f^3(n) = 8*r + 7 == 5 (mod 10), not prime, and a(n) <= 3.
(End)
From Peter Schorn, Jan 18 2021: (Start)
The Sophie Germain degree is always finite.
Proof. Let f^k(n) denote iterates of 2*k + 1 with closed form f^k(n) = 2^k * n + 2^k - 1.
There are three cases for n:
1. If n is not a prime then f^0(n) = n is composite.
2. If n = 2 then f^5(2) = 95 is composite.
3. If n is an odd prime then f^(n-1)(n) = 2^(n-1) * n + 2^(n-1) - 1 is divisible by n since 2^(n-1) == 1 (mod n) by Fermat's theorem.
(End)

			a(2)=5 because 2, 5, 11, 23, 47 are prime but 95 is not.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A005384, A063378, A093008, A093007, A292936, A339579.
For records see A339581.
See also Cunningham chains, A005602, A005603.

Table[Length[NestWhileList[2#+1&,n,PrimeQ[#]&]],{n,100}]-1 (* Harvey P. Dale, Aug 08 2020 *)

a(n) = {if (! isprime(n), return (0)); d = 1; k = n; while(isprime(p = 2*k+1), k = p; d++;); return (d);} \\ Michel Marcus, Jul 22 2013

From Michael S. Branicky, Dec 24 2020: (Start)
See proof above.
a(n) = 0 if n == 0, 2, 4, 5, 6, 8 (mod 10), and n != 2 or 5.
a(n) <= 1 if n == 7 (mod 10).
a(n) <= 2 if n == 3 (mod 10).
a(n) <= 3 if n == 1 (mod 10).
(End)

Term a(1) = 0 prepended by Antti Karttunen, Oct 09 2018.

A063378 Smallest number whose Sophie Germain degree (see A063377) is n.

Original entry on oeis.org

4, 7, 3, 11, 5, 2, 89, 1122659, 19099919, 85864769, 26089808579, 665043081119, 554688278429, 4090932431513069, 95405042230542329

Offset: 0

Reiner Martin, Jul 14 2001

Also known as Cunningham chains of length n of the first kind.

For each positive integer n, is there some integer with Sophie Germain degree of n?

			Using f(x)=2x+1, 11 -> 23 -> 47 -> 95, which is composite; thus a(3)=11.

Warut Roonguthai, Yves Gallot's Proth.exe and Cunningham Chains

Cf. A005384, A063377.

NextPrim[n_] := Block[{k = n + 1}, While[ !PrimeQ[k], k++ ]; k]; f[n_] := Block[{k = 2}, While[ Length[ NestWhileList[2# + 1 &, k, PrimeQ]] != n + 1, k = NextPrim[k]]; k]; Table[f[n], {n, 1, 8}]

More terms from Jud McCranie, Jul 20 2001

Edited and extended by Robert G. Wilson v, Nov 21 2002

A063650 Number of ways to tile a 6 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 13, 43, 269, 1213, 6427, 31387, 159651, 795611, 4005785, 20064827, 100764343, 505375405, 2536323145, 12724855013, 63851706457, 320373303983, 1607526474153, 8065864257905, 40471399479495, 203068825478591, 1018918472214687, 5112520236292975, 25652573037707685

Offset: 0

Reiner Martin, Jul 23 2001

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
R. J. Mathar, Tiling nXm rectangles with 1X1 and sXs squares arXiv:1609.03964 [math.CO] (2016) Section 4.1.
Index entries for linear recurrences with constant coefficients, signature (2,16,1,-27,1,4).

Cf. A001045, A054854, A054855, A063650-A063654.

Column k=6 of A245013.

I:=[1,1,13,43,269,1213]; [n le 6 select I[n] else 2*Self(n-1)+16*Self(n-2)+Self(n-3)-27*Self(n-4)+Self(n-5)+4*Self(n-6): n in [1..30]]; // Vincenzo Librandi, Oct 30 2018

LinearRecurrence[{2, 16, 1, -27, 1, 4}, {1, 1, 13, 43, 269, 1213}, 22] (* Jean-François Alcover, Oct 30 2018 *)
CoefficientList[Series[(-1+x+5*x^2-x^4)/(-1+2*x+16*x^2+x^3-27*x^4+x^5+4*x^6), {x, 0, 50}], x] (* Stefano Spezia, Oct 30 2018 *)

G.f.: ( -1+x+5*x^2-x^4 ) / ( -1+2*x+16*x^2+x^3-27*x^4+x^5+4*x^6 ).

a(n) = 2a(n-1) + 16a(n-2) + a(n-3) - 27a(n-4) + a(n-5) + 4a(n-6) - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006

A063651 Number of ways to tile a 7 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 21, 85, 747, 4375, 31387, 202841, 1382259, 9167119, 61643709, 411595537, 2758179839, 18448963469, 123518353059, 826573277157, 5532716266089, 37028886137273, 247839719105625, 1658772577825883, 11102227136885119

Offset: 0

Reiner Martin, Jul 23 2001

Index entries for linear recurrences with constant coefficients, signature (3,30,-17,-138,85,116,-42,-32).

Cf. A001045, A054854, A054855, A063650-A063654.

Column k=7 of A245013.

a(n) = 3a(n-1) + 30a(n-2) - 17a(n-3) - 138a(n-4) + 85a(n-5) + 116a(n-6) - 42a(n-7) - 32a(n-8). - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006

G.f.: ( 1 -2*x -12*x^2 +9*x^3 +17*x^4 -6*x^5 -6*x^6 ) / ( 1 -3*x -30*x^2 +17*x^3 +138*x^4 -85*x^5 -116*x^6 +42*x^7 +32*x^8 ). - Colin Barker, Nov 29 2012

A063653 Number of ways to tile a 9 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 55, 341, 5933, 59925, 795611, 9167119, 113555791, 1355115601, 16484061769, 198549329897, 2403674442213, 29023432116879, 350917980468767, 4239961392742933, 51247532773412135, 619304595300705203, 7484739788762129061, 90454037365096154821

Offset: 0

Reiner Martin, Jul 23 2001

nonn

a(8) is number of ways can kings be placed on an 8 X 8 chessboard so that no two kings can attack each other. - Vaclav Kotesovec, Apr 02 2010

Index entries for linear recurrences with constant coefficients, signature (6, 110, -262, -2786, 5916, 25168, -53907, -95299, 197820, 193866, -340168, -228528, 279636, 137864, -108909, -33736, 20214, 2460, -1296).

Cf. A001045, A054854, A054855, A063650, A063651, A063652, A063654.

Column k=9 of A245013.

a(n) = 6*a(n-1) + 110*a(n-2) - 262*a(n-3) - 2786*a(n-4) + 5916*a(n-5) + 25168*a(n-6) - 53907*a(n-7) - 95299*a(n-8) + 197820*a(n-9) + 193866*a(n-10) - 340168*a(n-11) - 228528*a(n-12) + 279636*a(n-13) + 137864*a(n-14) - 108909*a(n-15) - 33736*a(n-16) + 20214*a(n-17) + 2460*a(n-18) - 1296*a(n-19).

Subscripts in formula repaired by Ron Hardin, Dec 29 2010

A063654 Number of ways to tile a 10 X n rectangle with 1 X 1 and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 89, 683, 16717, 221799, 4005785, 61643709, 1029574631, 16484061769, 269718819131, 4364059061933, 71019435701025, 1152314664726905, 18725412666911121, 304052089851133193, 4939032362569285343

Offset: 0

Reiner Martin, Jul 23 2001

nonn

Index entries for linear recurrences with constant coefficients, signature (11, 195, -1459, -10427, 79002, 188873, -1922453, -522744, 21726132, -11085988, -137059276, 114023550, 533938164, -503739499, -1345858084, 1272444796, 2223076291, -1997887777, -2382027317, 2015253425, 1613022647, -1309632545, -660948344, 533727589, 152685069, -128889883, -17772195, 16954690, 883980, -1089264, -11392, 26112).

Cf. A001045, A054854, A054855, A063650-A063653.

Column k=10 of A245013.

a(n) = 11a(n-1) + 195a(n-2) - 1459a(n-3) - 10427a(n-4) + 79002a(n-5) + 188873a(n-6) - 1922453a(n-7) - 522744a(n-8) + 21726132a(n-9) - 11085988a(n-10) - 137059276a(n-11) + 114023550a(n-12) + 533938164a(n-13) - 503739499a(n-14) - 1345858084a(n-15) + 1272444796a(n-16) + 2223076291a(n-17) - 1997887777a(n-18) - 2382027317a(n-19) + 2015253425a(n-20) + 1613022647a(n-21) - 1309632545a(n-22) - 660948344a(n-23) + 533727589a(n-24) + 152685069a(n-25) - 128889883a(n-26) - 17772195a(n-27) + 16954690a(n-28) + 883980a(n-29) - 1089264a(n-30) - 11392a(n-31) + 26112a(n-32) - Keith Schneider (kschneid(AT)bulldog.unca.edu), Apr 02 2006

A066083 Number of supersolvable groups of order n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 4, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 12, 2, 2, 5, 4, 1, 4, 1, 51, 1, 2, 1, 11, 1, 2, 2, 14, 1, 6, 1, 4, 2, 2, 1, 42, 2, 5, 1, 5, 1, 15, 2, 12, 2, 2, 1, 11, 1, 2, 4, 267, 1, 4, 1, 5, 1, 4, 1, 37, 1, 2, 2, 4, 1, 6, 1, 51

Offset: 1

Reiner Martin, Dec 29 2001

A finite group is supersolvable if it has a normal series with cyclic factors. Huppert showed that a finite group is supersolvable iff the index of any maximal subgroup is prime.

B. Huppert, Über das Produkt von paarweise vertauschbaren zyklischen Gruppen, Math. Z. 58 (1954).

Cf. A000001, A066085.

A066085 Orders of non-supersolvable groups.

Original entry on oeis.org

12, 24, 36, 48, 56, 60, 72, 75, 80, 84, 96, 108, 112, 120, 132, 144, 150, 156, 160, 168, 180, 192, 196, 200, 204, 216, 224, 225, 228, 240, 252, 264, 276, 280, 288, 294, 300, 312, 320, 324, 336, 348, 351, 360, 363, 372, 375, 384, 392, 396, 400, 405, 408, 420

Offset: 1

Reiner Martin, Dec 29 2001

nonn

A finite group is supersolvable if it has a normal series with cyclic factors. Huppert showed that a finite group is supersolvable iff the index of any maximal subgroup is prime.

All multiples of non-supersolvable orders are non-supersolvable orders. - Des MacHale, Dec 22 2003

			a(1)=12 is in the sequence since the alternating group on 4 elements is the smallest group which is not supersolvable.

B. Huppert, Über das Produkt von paarweise vertauschbaren zyklischen Gruppen, Math. Z. 58 (1954).
Des MacHale and J. Manning, Converse Lagrange Theorem Orders and Supersolvable Orders, Journal of Integer Sequences, 2016, Vol. 19, #16.8.7.

Cf. A000001, A066083, A340511.

For primitive terms see A340517.

More terms from Des MacHale, Dec 22 2003

A066113 a(n) is the number of conjugacy classes of maximal subgroups of the alternating group A_n.

Original entry on oeis.org

0, 1, 2, 3, 5, 5, 6, 8, 7, 7, 11, 9, 9, 11, 12, 10, 13, 10, 14, 14, 13, 13, 19, 15, 15, 18, 20, 15, 21, 20, 22, 20, 18, 21, 27, 19, 21, 21, 27, 21, 27, 22, 26, 29, 24, 24, 32, 27, 31, 27, 31, 27, 33, 30, 35, 34, 30, 30, 41, 31, 33, 40, 40, 41, 40, 34, 39, 36, 40

Offset: 2

Reiner Martin, Dec 30 2001

nonn

Andrew Howroyd, Table of n, a(n) for n = 2..250
M. W. Liebeck, C. E. Praeger and J. Saxl, A classification of the maximal subgroups of the finite alternating and symmetric groups, J. Algebra 111(1987), no. 2, 365-383; Math. Rev. 89b:20008.

Cf. A029726, A066115, A316435.

List([2..50],i->Length(MaximalSubgroupClassReps(AlternatingGroup(i))));

More terms from Alexander Hulpke, Feb 19 2002

Terms a(51) and beyond from Andrew Howroyd, Jul 02 2018

A066853 Number of different remainders (or residues) for the Fibonacci numbers (A000045) when divided by n (i.e., the size of the set of F(i) mod n over all i).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 6, 9, 10, 7, 11, 9, 14, 15, 11, 13, 11, 12, 20, 9, 14, 19, 13, 25, 18, 27, 21, 10, 30, 19, 21, 19, 13, 35, 15, 29, 13, 25, 30, 19, 18, 33, 20, 45, 21, 15, 15, 37, 50, 35, 30, 37, 29, 12, 25, 33, 20, 37, 55, 25, 21, 23, 42, 45, 38, 51, 20, 29, 70, 44, 15, 57

Offset: 1

Reiner Martin, Jan 21 2002

nonn

The Fibonacci numbers mod n for any n are periodic - see A001175 for period lengths. - Ron Knott, Jan 05 2005

a(n) = number of nonzeros in n-th row of triangle A128924. - Reinhard Zumkeller, Jan 16 2014

			a(8)=6 since the Fibonacci numbers, 0,1,1,2,3,5,8,13,21,34,55,89,144,... when divided by 8 have remainders 0,1,1,2,3,5,0,5,5,2,7,1 (repeatedly) which only contains the remainders 0,1,2,3,5 and 7, i.e., 6 remainders, so a(8)=6.
a(11)=7 since Fibonacci numbers reduced modulo 11 are {0, 1, 2, 3, 5, 8, 10}.

T. D. Noe, Table of n, a(n) for n = 1..10000
Casey Mongoven, Sonification of multiple Fibonacci-related sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 175-192.

Cf. A001175, A079002.

a066853 1 = 1
a066853 n = f 1 ps [] where
   f 0 (1 : xs) ys = length ys
   f _ (x : xs) ys = if x `elem` ys then f x xs ys else f x xs (x:ys)
   ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
-- Reinhard Zumkeller, Jan 16 2014

a[n_] := Module[{v = {1, 2}}, If[n<8, n, While[v[[-1]] != 1 || v[[-2]] != 0, AppendTo[v, Mod[v[[-1]] + v[[-2]], n]]]; v // Union // Length]]; Array[a, 100] (* Jean-François Alcover, Feb 15 2018, after Charles R Greathouse IV *)

a(n)=if(n<8, return(n)); my(v=List([1,2])); while(v[#v]!=1 || v[#v-1]!=0, listput(v, (v[#v]+v[#v-1])%n)); #Set(v) \\ Charles R Greathouse IV, Jun 19 2017

cp's OEIS Frontend

User: Reiner Martin

A063377 Sophie Germain degree of n: number of iterations of n under f(k) = 2k+1 before we reach a number that is not a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A063378 Smallest number whose Sophie Germain degree (see A063377) is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A063650 Number of ways to tile a 6 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A063651 Number of ways to tile a 7 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Links

Crossrefs

Formula

A063653 Number of ways to tile a 9 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A063654 Number of ways to tile a 10 X n rectangle with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Links

Crossrefs

Formula

A066083 Number of supersolvable groups of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

A066085 Orders of non-supersolvable groups.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A066113 a(n) is the number of conjugacy classes of maximal subgroups of the alternating group A_n.

Views

Author

Keywords

Links