cp's OEIS Frontend

A380978(n) is defined as the minimal Fermat witness that guarantees the compositeness of a(n). See the Weisstein link for details of the guarantee -- the option that uses a property derived from Fermat's little theorem.

To what extent does this differ from A135720 sorted? - Peter Munn, Mar 12 2025

Can be extended to negative numbers by defining a(-n) = -a(n).

Based on the product rule for differentiation of functions: for functions f(x) and g(x), (fg)' = f'g + fg'. So with numbers, (ab)' = a'b + ab'. This implies 1' = 0. - Kerry Mitchell, Mar 18 2004

The derivative of a number x with respect to a prime number p as being the number "dx/dp" = (x-x^p)/p, which is an integer due to Fermat's little theorem. - Alexandru Buium, Mar 18 2004

The relation (ab)' = a'b + ab' implies 1' = 0, but it does not imply p' = 1 for p a prime. In fact, any function f defined on the primes can be extended uniquely to a function on the integers satisfying this relation: f(Product_i p_i^e_i) = (Product_i p_i^e_i) * (Sum_i e_i*f(p_i)/p_i). - Franklin T. Adams-Watters, Nov 07 2006

See A131116 and A131117 for record values and where they occur. - Reinhard Zumkeller, Jun 17 2007

Let n be the product of a multiset P of k primes. Consider the k-dimensional box whose edges are the elements of P. Then the (k-1)-dimensional surface of this box is 2*a(n). For example, 2*a(25) = 20, the perimeter of a 5 X 5 square. Similarly, 2*a(18) = 42, the surface area of a 2 X 3 X 3 box. - David W. Wilson, Mar 11 2011

The arithmetic derivative n' was introduced, probably for the first time, by the Spanish mathematician José Mingot Shelly in June 1911 with "Una cuestión de la teoría de los números", work presented at the "Tercer Congreso Nacional para el Progreso de las Ciencias, Granada", cf. link to the abstract on Zentralblatt MATH, and L. E. Dickson, History of the Theory of Numbers. - Giorgio Balzarotti, Oct 19 2013

a(A235991(n)) odd; a(A235992(n)) even. - Reinhard Zumkeller, Mar 11 2014

Sequence A157037 lists numbers with prime arithmetic derivative, i.e., indices of primes in this sequence. - M. F. Hasler, Apr 07 2015

Maybe the simplest "natural extension" of the arithmetic derivative, in the spirit of the above remark by Franklin T. Adams-Watters (2006), is the "pi based" version where f(p) = primepi(p), see sequence A258851. When f is chosen to be the identity map (on primes), one gets A066959. - M. F. Hasler, Jul 13 2015

When n is composite, it appears that a(n) has lower bound 2*sqrt(n), with equality when n is the square of a prime, and a(n) has upper bound (n/2)*log_2(n), with equality when n is a power of 2. - Daniel Forgues, Jun 22 2016

If n = p1*p2*p3*... where p1, p2, p3, ... are all the prime factors of n (not necessarily distinct), and h is a real number (we assume h nonnegative and < 1), the arithmetic derivative of n is equivalent to n' = lim_{h->0} ((p1+h)*(p2+h)*(p3+h)*... - (p1*p2*p3*...))/h. It also follows that the arithmetic derivative of a prime is 1. We could assume h = 1/N, where N is an integer; then the limit becomes {N -> oo}. Note that n = 1 is not a prime and plays the role of constant. - Giorgio Balzarotti, May 01 2023

Also, solutions to phi(n + 2) = sigma(n). - Conjectured by Jud McCranie, Jan 03 2001; proved by Reinhard Zumkeller, Dec 05 2002

The set of primes for which the weight as defined in A117078 is 3 gives this sequence except for the initial 3. - Rémi Eismann, Feb 15 2007

The set of lesser of twin primes larger than three is a proper subset of the set of primes of the form 3n - 1 (A003627). - Paul Muljadi, Jun 05 2008

It is conjectured that A113910(n+4) = a(n+2) for all n. - Creighton Dement, Jan 15 2009

I would like to conjecture that if f(x) is a series whose terms are x^n, where n represents the terms of sequence A001359, and if we inspect {f(x)}^5, the conjecture is that every term of the expansion, say a_n * x^n, where n is odd and at least equal to 15, has a_n >= 1. This is not true for {f(x)}^k, k = 1, 2, 3 or 4, but appears to be true for k >= 5. - Paul Bruckman (pbruckman(AT)hotmail.com), Feb 03 2009

A164292(a(n)) = 1; A010051(a(n) - 2) = 0 for n > 1. - Reinhard Zumkeller, Mar 29 2010

From Jonathan Sondow, May 22 2010: (Start)

About 15% of primes < 19000 are the lesser of twin primes. About 26% of Ramanujan primes A104272 < 19000 are the lesser of twin primes.

About 46% of primes < 19000 are Ramanujan primes. About 78% of the lesser of twin primes < 19000 are Ramanujan primes.

A reason for the jumps is in Section 7 of "Ramanujan primes and Bertrand's postulate" and in Section 4 of "Ramanujan Primes: Bounds, Runs, Twins, and Gaps". (End)

Primes generated by sequence A040976. - Odimar Fabeny, Jul 12 2010

Primes of the form 2*n - 3 with 2*n - 1 prime n > 2. Primes of the form (n^2 - (n-2)^2)/2 - 1 with (n^2 - (n-2)^2)/2 + 1 prime so sum of two consecutive odd numbers/2 - 1. - Pierre CAMI, Jan 02 2012

Conjecture: For any integers n >= m > 0, there are infinitely many integers b > a(n) such that the number Sum_{k=m..n} a(k)*b^(n-k) (i.e., (a(m), ..., a(n)) in base b) is prime; moreover, when m = 1 there is such an integer b < (n+6)^2. - Zhi-Wei Sun, Mar 26 2013

Except for the initial 3, all terms are congruent to 5 mod 6. One consequence of this is that no term of this sequence appears in A030459. - Alonso del Arte, May 11 2013

Aside from the first term, all terms have digital root 2, 5, or 8. - J. W. Helkenberg, Jul 24 2013

The sequence provides all solutions to the generalized Winkler conjecture (A051451) aside from all multiples of 6. Specifically, these solutions start from n = 3 as a(n) - 3. This gives 8, 14, 26, 38, 56, ... An example from the conjecture is solution 38 from twin prime pairs (3, 5), (41, 43). - Bill McEachen, May 16 2014

Conjecture: a(n)^(1/n) is a strictly decreasing function of n. Namely a(n+1)^(1/(n+1)) < a(n)^(1/n) for all n. This conjecture is true for all a(n) <= 1121784847637957. - Jahangeer Kholdi and Farideh Firoozbakht, Nov 21 2014

a(n) are the only primes, p(j), such that (p(j+m) - p(j)) divides (p(j+m) + p(j)) for some m > 0, where p(j) = A000040(j). For all such cases m=1. It is easy to prove, for j > 1, the only common factor of (p(j+m) - p(j)) and (p(j+m) + p(j)) is 2, and there are no common factors if j = 1. Thus, p(j) and p(j+m) are twin primes. Also see A067829 which includes the prime 3. - Richard R. Forberg, Mar 25 2015

Primes prime(k) such that prime(k)! == 1 (mod prime(k+1)) with the exception of prime(991) = 7841 and other unknown primes prime(k) for which (prime(k)+1)*(prime(k)+2)*...*(prime(k+1)-2) == 1 (mod prime(k+1)) where prime(k+1) - prime(k) > 2. - Thomas Ordowski and Robert Israel, Jul 16 2016

For the twin prime criterion of Clement see the link. In Ribenboim, pp. 259-260 a more detailed proof is given. - Wolfdieter Lang, Oct 11 2017

Conjecture: Half of the twin prime pairs can be expressed as 8n + M where M > 8n and each value of M is a distinct composite integer with no more than two prime factors. For example, when n=1, M=21 as 8 + 21 = 29, the lesser of a twin prime pair. - Martin Michael Musatov, Dec 14 2017

For a discussion of bias in the distribution of twin primes, see my article on the Vixra web site. - Waldemar Puszkarz, May 08 2018

Since 2^p == 2 (mod p) (Fermat's little theorem), these are primes p such that 2^p == q (mod p), where q is the next prime after p. - Thomas Ordowski, Oct 29 2019, edited by M. F. Hasler, Nov 14 2019

The yet unproved "Twin Prime Conjecture" states that this sequence is infinite. - M. F. Hasler, Nov 14 2019

Lesser of the twin primes are the set of elements that occur in both A162566, A275697. Proof: A prime p will only have integer solutions to both (p+1)/g(p) and (p-1)/g(p) when p is the lesser of a twin prime, where g(p) is the gap between p and the next prime, because gcd(p+1,p-1) = 2. - Ryan Bresler, Feb 14 2021

From Lorenzo Sauras Altuzarra, Dec 21 2021: (Start)

J. A. Hervás Contreras observed the subsequence 11, 311, 18311, 1518311, 421518311... (see the links), which led me to conjecture the following statements.

I. If i is an integer greater than 2, then there exist positive integers j and k such that a(j) equals the concatenation of 3k and a(i).

II. If k is a positive integer, then there exist positive integers i and j such that a(j) equals the concatenation of 3k and a(i).

III. If i, j, and r are positive integers such that i > 2 and a(j) equals the concatenation of r and a(i), then 3 divides r. (End)

An n X n nonnegative matrix A is primitive (see A070322) iff every element of A^k is > 0 for some power k. If A is primitive then the power which should have all positive entries is <= n^2 - 2n + 2 (Wielandt).

a(n) = Phi_4(n), where Phi_k is the k-th cyclotomic polynomial.

As the positive solution to x=2n+1/x is x=n+sqrt(a(n)), the continued fraction expansion of sqrt(a(n)) is {n; 2n, 2n, 2n, 2n, ...}. - Benoit Cloitre, Dec 07 2001

a(n) is one less than the arithmetic mean of its neighbors: a(n) = (a(n-1) + a(n+1))/2 - 1. E.g., 2 = (1+5)/2 - 1, 5 = (2+10)/2 - 1. - Amarnath Murthy, Jul 29 2003

Equivalently, the continued fraction expansion of sqrt(a(n)) is (n;2n,2n,2n,...). - Franz Vrabec, Jan 23 2006

Number of {12,1*2*,21}-avoiding signed permutations in the hyperoctahedral group.

The number of squares of side 1 which can be drawn without lifting the pencil, starting at one corner of an n X n grid and never visiting an edge twice is n^2-2n+2. - Sébastien Dumortier, Jun 16 2005

Also, numbers m such that m^3 - m^2 is a square, (n*(1 + n^2))^2. - Zak Seidov

1 + 2/2 + 2/5 + 2/10 + ... = Pi*coth Pi [Jolley], see A113319. - Gary W. Adamson, Dec 21 2006

For n >= 1, a(n-1) is the minimal number of choices from an n-set such that at least one particular element has been chosen at least n times or each of the n elements has been chosen at least once. Some games define "matches" this way; e.g., in the classic Parker Brothers, now Hasbro, board game Risk, a(2)=5 is the number of cards of three available types (suits) required to guarantee at least one match of three different types or of three of the same type (ignoring any jokers or wildcards). - Rick L. Shepherd, Nov 18 2007

Positive X values of solutions to the equation X^3 + (X - 1)^2 + X - 2 = Y^2. To prove that X = n^2 + 1: Y^2 = X^3 + (X - 1)^2 + X - 2 = X^3 + X^2 - X - 1 = (X - 1)(X^2 + 2X + 1) = (X - 1)*(X + 1)^2 it means: (X - 1) must be a perfect square, so X = n^2 + 1 and Y = n(n^2 + 2). - Mohamed Bouhamida, Nov 29 2007

{a(k): 0 <= k < 4} = divisors of 10. - Reinhard Zumkeller, Jun 17 2009

Appears in A054413 and A086902 in relation to sequences related to the numerators and denominators of continued fractions convergents to sqrt((2*n)^2/4 + 1), n=1, 2, 3, ... . - Johannes W. Meijer, Jun 12 2010

For n > 0, continued fraction [n,n] = n/a(n); e.g., [5,5] = 5/26. - Gary W. Adamson, Jul 15 2010

The only real solution of the form f(x) = A*x^p with negative p which satisfies f^(m)(x) = f^[-1](x), x >= 0, m >= 1, with f^(m) the m-th derivative and f^[-1] the compositional inverse of f, is obtained for m=2*n, p=p(n)= -(sqrt(a(n))-n) and A=A(n)=(fallfac(p(n),2*n))^(-p(n)/(p(n)+1)), with fallfac(x,k):=Product_{j=0..k-1} (x-j) (falling factorials). See the T. Koshy reference, pp. 263-4 (there are also two solutions for positive p, see the corresponding comment in A087475). - Wolfdieter Lang, Oct 21 2010

n + sqrt(a(n)) = [2*n;2*n,2*n,...] with the regular continued fraction with period 1. This is the even case. For the general case see A087475 with the Schroeder reference and comments. For the odd case see A078370.

a(n-1) counts configurations of non-attacking bishops on a 2 X n strip [Chaiken et al., Ann. Combin. 14 (2010) 419]. - R. J. Mathar, Jun 16 2011

Also numbers k such that 4*k-4 is a square. Hence this sequence is the union of A053755 and A069894. - Arkadiusz Wesolowski, Aug 02 2011

a(n) is also the Moore lower bound on the order, A191595(n), of an (n,5)-cage. - Jason Kimberley, Oct 17 2011

Left edge of the triangle in A195437: a(n+1) = A195437(n,0). - Reinhard Zumkeller, Nov 23 2011

If h (5,17,37,65,101,...) is prime is relatively prime to 6, then h^2-1 is divisible by 24. - Vincenzo Librandi, Apr 14 2014

The identity (4*n^2+2)^2 - (n^2+1)*(4*n)^2 = 4 can be written as A005899(n)^2 - a(n)*A008586(n)^2 = 4. - Vincenzo Librandi, Jun 15 2014

a(n) is also the number of permutations simultaneously avoiding 213 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl, Aug 07 2014

a(n-1) is the maximum number of stages in the Gale-Shapley algorithm for finding a stable matching between two sets of n elements given an ordering of preferences for each element (see Gura et al.). - Melvin Peralta, Feb 07 2016

Because of Fermat's little theorem, a(n) is never divisible by 3. - Altug Alkan, Apr 08 2016

For n > 0, if a(n) points are placed inside an n X n square, it will always be the case that at least two of the points will be a distance of sqrt(2) units apart or less. - Melvin Peralta, Jan 21 2017

Also the limit as q->1^- of the unimodal polynomial (1-q^(n*k+1))/(1-q) after making the simplification k=n. The unimodal polynomial is from O'Hara's proof of unimodality of q-binomials after making the restriction to partitions of size <= 1. See G_1(n,k) from arXiv:1711.11252. As the size restriction s increases, G_s->G_infinity=G: the q-binomials. Then substituting k=n and q=1 yields the central binomial coefficients: A000984. - Bryan T. Ek, Apr 11 2018

a(n) is the smallest number congruent to both 1 (mod n) and 2 (mod n+1). - David James Sycamore, Apr 04 2019

a(n) is the number of permutations of 1,2,...,n+1 with exactly one reduced decomposition. - Richard Stanley, Dec 22 2022

From Klaus Purath, Apr 03 2025: (Start)

The odd prime factors of these terms are always of the form 4*k + 1.

All a(n) = D satisfy the Pell equation (k*x)^2 - D*y^2 = -1. The values for k and the solutions x, y can be calculated using the following algorithm: k = n, x(0) = 1, x(1) = 4*D - 1, y(0) = 1, y(1) = 4*D - 3. The two recurrences are of the form (4*D - 2, -1). The solutions x, y of the Pell equations for n = {1 ... 14} are in OEIS.

It follows from the above that this sequence is a subsequence of A031396. (End)

A composite number n is a Fermat pseudoprime to base b if and only if b^(n-1) == 1 (mod n). Fermat pseudoprimes to base 2 are often simply called pseudoprimes.

Theorem: If both numbers q and 2q - 1 are primes (q is in the sequence A005382) and n = q*(2q-1) then 2^(n-1) == 1 (mod n) (n is in the sequence) if and only if q is of the form 12k + 1. The sequence 2701, 18721, 49141, 104653, 226801, 665281, 721801, ... is related. This subsequence is also a subsequence of the sequences A005937 and A020137. - Farideh Firoozbakht, Sep 15 2006

Also, composite odd numbers n such that n divides 2^n - 2 (cf. A006935). It is known that all primes p divide 2^(p-1) - 1. There are only two known numbers n such that n^2 divides 2^(n-1) - 1, A001220(n) = {1093, 3511} Wieferich primes p: p^2 divides 2^(p-1) - 1. 1093^2 and 3511^2 are the terms of a(n). - Alexander Adamchuk, Nov 06 2006

An odd composite number 2n + 1 is in the sequence if and only if multiplicative order of 2 (mod 2n+1) divides 2n. - Ray Chandler, May 26 2008

The Carmichael numbers A002997 are a subset of this sequence. For the Sarrus numbers which are not Carmichael numbers, see A153508. - Artur Jasinski, Dec 28 2008

An odd number n greater than 1 is a Fermat pseudoprime to base b if and only if ((n-1)! - 1)*b^(n-1) == -1 (mod n). - Arkadiusz Wesolowski, Aug 20 2012

The name "Sarrus numbers" is after Frédéric Sarrus, who, in 1819, discovered that 341 is a counterexample to the "Chinese hypothesis" that n is prime if and only if 2^n is congruent to 2 (mod n). - Alonso del Arte, Apr 28 2013

The name "Poulet numbers" appears in Monografie Matematyczne 42 from 1932, apparently because Poulet in 1928 produced a list of these numbers (cf. Miller, 1975). - Felix Fröhlich, Aug 18 2014

Numbers n > 2 such that (n-1)! + 2^(n-1) == 1 (mod n). Composite numbers n such that (n-2)^(n-1) == 1 (mod n). - Thomas Ordowski, Feb 20 2016

The only twin pseudoprimes up to 10^13 are 4369, 4371. - Thomas Ordowski, Feb 12 2016

Theorem (A. Rotkiewicz, 1965): (2^p-1)*(2^q-1) is a pseudoprime if and only if p*q is a pseudoprime, where p,q are different primes. - Thomas Ordowski, Mar 31 2016

Theorem (W. Sierpiński, 1947): if n is a pseudoprime (odd or even), then 2^n-1 is a pseudoprime. - Thomas Ordowski, Apr 01 2016

If 2^n-1 is a pseudoprime, then n is a prime or a pseudoprime (odd or even). - Thomas Ordowski, Sep 05 2016

From Amiram Eldar, Jun 19 2021, Apr 21 2024: (Start)

Erdős (1950) called these numbers "almost primes".

According to Erdős (1949) and Piza (1954), the term "pseudoprime" was coined by D. H. Lehmer.

Named after the French mathematician Pierre de Fermat (1607-1665), or, alternatively, after the Belgian mathematician Paul Poulet (1887-1946), or, the French mathematician Pierre Frédéric Sarrus (1798-1861). (End)

If m is a term of this sequence, then (m-1)/ord(2,m) >= 5, where ord(a,m) is the multiplicative order of a modulo m; see my link below. Actually, it seems that we always have (m-1)/ord(2,m) >= 9. - Jianing Song, Nov 04 2024

V. Šimerka found the first 7 terms of this sequence 25 years before Carmichael (see the link and also the remark of K. Conrad). - Peter Luschny, Apr 01 2019

k is composite and squarefree and for p prime, p|k => p-1|k-1.

An odd composite number k is a pseudoprime to base a iff a^(k-1) == 1 (mod k). A Carmichael number is an odd composite number k which is a pseudoprime to base a for every number a prime to k.

A composite odd number k is a Carmichael number if and only if k is squarefree and p-1 divides k-1 for every prime p dividing k. (Korselt, 1899)

Ghatage and Scott prove using Fermat's little theorem that (a+b)^k == a^k + b^k (mod k) (the freshman's dream) exactly when k is a prime (A000040) or a Carmichael number. - Jonathan Vos Post, Aug 31 2005

Alford et al. have constructed a Carmichael number with 10333229505 prime factors, and have also constructed Carmichael numbers with m prime factors for every m between 3 and 19565220. - Jonathan Vos Post, Apr 01 2012

Thomas Wright proved that for any numbers b and M in N with gcd(b,M) = 1, there are infinitely many Carmichael numbers k such that k == b (mod M). - Jonathan Vos Post, Dec 27 2012

Composite numbers k relatively prime to 1^(k-1) + 2^(k-1) + ... + (k-1)^(k-1). - Thomas Ordowski, Oct 09 2013

Composite numbers k such that A063994(k) = A000010(k). - Thomas Ordowski, Dec 17 2013

Odd composite numbers k such that k divides A002445((k-1)/2). - Robert Israel, Oct 02 2015

If k is a Carmichael number and gcd(b-1,k)=1, then (b^k-1)/(b-1) is a pseudoprime to base b by Steuerwald's theorem; see the reference in A005935. - Thomas Ordowski, Apr 17 2016

Composite numbers k such that p^k == p (mod k) for every prime p <= A285512(k). - Max Alekseyev and Thomas Ordowski, Apr 20 2017

If a composite m < A285549(n) and p^m == p (mod m) for every prime p <= prime(n), then m is a Carmichael number. - Thomas Ordowski, Apr 23 2017

The sequence of all Carmichael numbers can be defined as follows: a(1) = 561, a(n+1) = smallest composite k > a(n) such that p^k == p (mod k) for every prime p <= n+2. - Thomas Ordowski, Apr 24 2017

An integer m > 1 is a Carmichael number if and only if m is squarefree and each of its prime divisors p satisfies both s_p(m) >= p and s_p(m) == 1 (mod p-1), where s_p(m) is the sum of the base-p digits of m. Then m is odd and has at least three prime factors. For each prime factor p, the sharp bound p <= a*sqrt(m) holds with a = sqrt(17/33) = 0.7177.... See Kellner and Sondow 2019. - Bernd C. Kellner and Jonathan Sondow, Mar 03 2019

Carmichael numbers are special polygonal numbers A324973. The rank of the n-th Carmichael number is A324975(n). See Kellner and Sondow 2019. - Jonathan Sondow, Mar 26 2019

An odd composite number m is a Carmichael number iff m divides denominator(Bernoulli(m-1)). The quotient is A324977. See Pomerance, Selfridge, & Wagstaff, p. 1006, and Kellner & Sondow, section on Bernoulli numbers. - Jonathan Sondow, Mar 28 2019

This is setwise difference A324050 \ A008578. Many of the same identities apply also to A324050. - Antti Karttunen, Apr 22 2019

If k is a Carmichael number, then A309132(k) = A326690(k). The proof generalizes that of Theorem in A309132. - Jonathan Sondow, Jul 19 2019

Composite numbers k such that A111076(k)^(k-1) == 1 (mod k). Proof: the multiplicative order of A111076(k) mod k is equal to lambda(k), where lambda(k) = A002322(k), so lambda(k) divides k-1, qed. - Thomas Ordowski, Nov 14 2019

For all positive integers m, m^k - m is divisible by k, for all k > 1, iff k is either a Carmichael number or a prime, as is used in the proof by induction for Fermat's Little Theorem. Also related are A182816 and A121707. - Richard R. Forberg, Jul 18 2020

From Amiram Eldar, Dec 04 2020, Apr 21 2024: (Start)

Ore (1948) called these numbers "Numbers with the Fermat property", or, for short, "F numbers".

Also called "absolute pseudoprimes". According to Erdős (1949) this term was coined by D. H. Lehmer.

Named by Beeger (1950) after the American mathematician Robert Daniel Carmichael (1879 - 1967). (End)

For ending digit 1,3,5,7,9 through the first 10000 terms, we see 80.3, 4.1, 7.4, 3.8 and 4.3% apportionment respectively. Why the bias towards ending digit "1"? - Bill McEachen, Jul 16 2021

It seems that for any m > 1, the remainders of Carmichael numbers modulo m are biased towards 1. The number of terms congruent to 1 modulo 4, 6, 8, ..., 24 among the first 10000 terms: 9827, 9854, 8652, 8034, 9682, 5685, 6798, 7820, 7880, 3378 and 8518. - Jianing Song, Nov 08 2021

Alford, Granville and Pomerance conjectured in their 1994 paper that a statement analogous to Bertrand's Postulate could be applied to Carmichael numbers. This has now been proved by Daniel Larsen, see link below. - David James Sycamore, Jan 17 2023

a(n) is the size of largest conjugacy class in D_2n, the dihedral group with 2n elements. - Sharon Sela (sharonsela(AT)hotmail.com), May 14 2002

a(n+1) is the composition length of the n-th symmetric power of the natural representation of a finite subgroup of SL(2,C) of type D_4 (quaternion group). - Paul Boddington, Oct 23 2003

For n > 1, a(n) is the greatest common divisor of all permutations of {0, 1, ..., n} treated as base n + 1 integers. - David Scambler, Nov 08 2006 (see the Mathematics Stack Exchange link below).

From Dimitrios Choussos (choussos(AT)yahoo.de), May 11 2009: (Start)

Sequence A075888 and the above sequence are fitting together.

First 2 entries of this sequence have to be taken out.

In some cases two three or more sequenced entries of this sequence have to be added together to get the next entry of A075888.

Example: Sequences begin with 1, 3, 2, 5, 3, 7, 4, 9 (4 + 9 = 13, the next entry in A075888).

But it works out well up to primes around 50000 (haven't tested higher ones).

As A075888 gives a very regular graph. There seems to be a regularity in the primes. (End)

Starting with 1 = triangle A115359 * [1, 2, 3, ...]. - Gary W. Adamson, Nov 27 2009

From Gary W. Adamson, Dec 11 2009: (Start)

Let M be an infinite lower triangular matrix with (1, 1, 1, 0, 0, 0, ...) in every column, shifted down twice. This sequence starting with 1 = M * (1, 2, 3, ...)

M =

1;

1, 0;

1, 1, 0;

0, 1, 0, 0;

0, 1, 1, 0, 0;

0, 0, 1, 0, 0, 0;

0, 0, 1, 1, 0, 0, 0;

...

A026741 = M * (1, 2, 3, ...); but A002487 = lim_{n->infinity} M^n, a left-shifted vector considered as a sequence. (End)

A particular case of sequence for which a(n+3) = (a(n+2) * a(n+1)+q)/a(n) for every n > n0. Here n0 = 1 and q = -1. - Richard Choulet, Mar 01 2010

For n >= 2, a(n+1) is the smallest m such that s_n(2*m*(n-1))/(n-1) is even, where s_b(c) is the sum of digits of c in base b. - Vladimir Shevelev, May 02 2011

A001477 and A005408 interleaved. - Omar E. Pol, Aug 22 2011

Numerator of n/((n-1)*(n-2)). - Michael B. Porter, Mar 18 2012

Number of odd terms of n-th row in the triangles A162610 and A209297. - Reinhard Zumkeller, Jan 19 2013

For n >= 3, a(n) is the periodic of integer of spiral length ratio of spiral that have (n-1) circle centers. See illustration in links. - Kival Ngaokrajang, Dec 28 2013

This is the sequence of Lehmer numbers u_n(sqrt(R), Q) with the parameters R = 4 and Q = 1. It is a strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all natural numbers n and m. Cf. A005013 and A108412. - Peter Bala, Apr 18 2014

The sequence of convergents of the 2-periodic continued fraction [0; 1, -4, 1, -4, ...] = 1/(1 - 1/(4 - 1/(1 - 1/(4 - ...)))) = 2 begins [0/1, 1/1, 4/3, 3/2, 8/5, 5/3, 12/7, ...]. The present sequence is the sequence of denominators; the sequence of numerators of the continued fraction convergents [0, 1, 4, 3, 8, 5, 12, ...] is A022998, also a strong divisibility sequence. - Peter Bala, May 19 2014

For n >= 3, (a(n-2)/a(n))*Pi = vertex angle of a regular n-gon. See illustration in links. - Kival Ngaokrajang, Jul 17 2014

For n > 1, the numerator of the harmonic mean of the first n triangular numbers. - Colin Barker, Nov 13 2014

The difference sequence is a permutation of the integers. - Clark Kimberling, Apr 19 2015

From Timothy Hopper, Feb 26 2017: (Start)

Given the function a(n, p) = n/p if n mod p = 0, else n, then a possible formula is: a(n, p) = n*(1 + (p-1)*((n^(p-1)) mod p))/p, p prime, (n^(p-1)) mod p = 1, n not divisible by p. (Fermat's Little Theorem). Examples: p = 2; a(n), p = 3; A051176(n), p = 5; A060791(n), p = 7; A106608(n).

Conjecture: lcm(n, p) = p*a(n, p), gcd(n, p) = n/a(n, p). (End)

Let r(n) = (a(n+1) + 1)/a(n+1) if n mod 2 = 1, a(n+1)/(a(n+1) + 2) otherwise; then lim_{k->oo} 2^(k+2) * Product_{n=0..k} r(n)^(k-n) = Pi. - Dimitris Valianatos, Mar 22 2021

Number of integers k from 1 to n such that gcd(n,k) is odd. - Amiram Eldar, May 18 2025

Drop initial 2; then iterates of A050411 do not diverge for these starting values. - David W. Wilson

All nonnegative integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = +4 together with b(n)=A001906(n), n>=0. - Wolfdieter Lang, Aug 31 2004

a(n+1) = B^(n)AB(1), n>=0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 3=`10`, 7=`010`, 18=`0010`, 47=`00010`, ..., in Wythoff code. a(0) = 2 = B(1) in Wythoff code.

Output of Tesler's formula (as well as that of Lu and Wu) for the number of perfect matchings of an m X n Möbius band where m and n are both even specializes to this sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009

Numbers having two 1's in their base-phi representation. - Robert G. Wilson v, Sep 13 2010

Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... - R. J. Mathar, Aug 10 2012

From Wolfdieter Lang, Feb 18 2013: (Start)

a(n) is also one half of the total number of round trips, each of length 2*n, on the graph P_4 (o-o-o-o) (the simple path with 4 points (vertices) and 3 lines (or edges)). See the array and triangle A198632 for the general case of the graph P_N (there N is n and the length is l=2*k).

O.g.f. for w(4,l) (with zeros for odd l): y*(d/dy)S(4,y)/S(4,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See also A198632 for a rewritten form. One half of this o.g.f. for x -> sqrt(x) produces the g.f. (2-3x)/(1-3x+x^2) given below. (End)

Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy - 5. - Michel Lagneau, Feb 01 2014

Except for the first term, positive values of x (or y) satisfying x^2 - 7xy + y^2 + 45 = 0. - Colin Barker, Feb 16 2014

Except for the first term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 320 = 0. - Colin Barker, Feb 16 2014

a(n) are the numbers such that a(n)^2-2 are Lucas numbers. - Michel Lagneau, Jul 22 2014

All sequences of this form, b(n+1) = 3*b(n) - b(n-1), regardless of initial values, which includes this sequence, yield this sequence as follows: a(n) = (b(j+n) + b(j-n))/b(j), for any j, except where b(j) = 0. Also note formula below relating this a(n) to all sequences of the form G(n+1) = G(n) + G(n-1). - Richard R. Forberg, Nov 18 2014

A non-simple continued fraction expansion for F(2n*(k+1))/F(2nk) k>=1 is a(n) + (-1)/(a(n) + (-1)/(a(n) + ... + (-1)/a(n))) where a(n) appears exactly k times (F(n) denotes the n-th Fibonacci number). E.g., F(16)/F(12) equals 7 + (-1)/(7 + (-1)/7). Furthermore, these a(n) are exactly the positive integers k such that the non-simple infinite continued fraction k + (-1)/(k + (-1)/(k + (-1)/(k + ...))) belongs to Q(sqrt(5)). Compare to Benoit Cloitre and Thomas Baruchel's comments at A002878. - Greg Dresden, Aug 13 2019

For n >= 1, a(n) is the number of cyclic up-down words of length 2*n over an alphabet of size 3. - Sela Fried, Apr 08 2025

a(16) > 10^14 if it exists. - Anders Kaseorg, Dec 02 2020

Conjecture: There are no terms that are 3 or 9 modulo 12. This seems to hold for all related sequences with even powers of primes, not just squares. Compare "sums of powers of primes divisibility sequences", linked below. - Daniel Bamberger, Dec 03 2020

From Jacob Christian Munch-Andersen, Dec 13 2020: (Start)

Any prime except 3 raised to the 2nd power is 1 modulo 3. Therefore adding the squared primes together results in a simple periodic pattern modulo 3. Any term that is 0 modulo 3 would imply that it divides a number that is 2 modulo 3; as this is impossible there cannot be any terms divisible by 3.

The same proof indeed holds for similar lists generated with any even power, and a similar proof for instance disqualifies any multiple of 5 from the similar 4th-power list. A slightly simpler similar proof shows that there are no terms divisible by 2.

(End)

The previous comment implies that for a list generated with the m-th power, there are no terms divisible by p when p is prime and p-1 is a divisor of m. For example, the 12th power list has no terms divisible by 2, 3, 5, 7 or 13. - Paul W. Dyson, Jan 09 2021

The periodic pattern of the sum of primes raised to an even power as described in the comments above follows from Fermat's little theorem. When the pattern is periodic for a given p it can be seen that when k mod p = 0 the sum mod p = p-1 and therefore sum mod k cannot be 0. - Bruce Garner, Apr 08 2021

a(2) is also a value in each of the lists generated with the powers 20, 38, 56... . a(3) is also a value in each of the lists generated with the powers 38, 74, 110... . In general, if the sum of the first k primes each to the power of m is divisible by k, and m >= the maximum exponent in the prime factorization of k, then the sum of the first k primes each to the power of m + j * psi(k) is also divisible by k, where psi(k) is the reduced totient function (A002322) and j is any positive integer. This follows from the fact that n^m == n^(m + psi(k)) (mod k) for all integers n and all integers m >= the maximum exponent in the prime factorization of k. - Paul W. Dyson, Dec 09 2022

a(17) > 8*10^15. - Paul W. Dyson, Jan 16 2025

For n >= 3, a(n) is the number of cyclic sequences consisting of n zeros and ones that do not contain three consecutive ones provided the positions of the zeros and ones are fixed on a circle. This is proved in Charalambides (1991) and Zhang and Hadjicostas (2015). For example, a(3)=7 because only the sequences 110, 101, 011, 001, 010, 100 and 000 avoid three consecutive ones. (For n=1,2 the statement is still true provided we allow the sequence to wrap around itself on a circle.) - Petros Hadjicostas, Dec 16 2016

For n >= 3, also the number of dominating sets on the n-cycle graph C_n. - Eric W. Weisstein, Mar 30 2017

For n >= 3, also the number of minimal dominating sets and maximal irredundant sets on the n-sun graph. - Eric W. Weisstein, Jul 28 and Aug 17 2017

For n >= 3, also the number of minimal edge covers in the n-web graph. - Eric W. Weisstein, Aug 03 2017

For n >= 1, also the number of ways to tile a bracelet of length n with squares, dominoes, and trominoes. - Ruijia Li and Greg Dresden, Sep 14 2019

If n is prime, then a(n)-1 is a multiple of n ; a counterexample for the converse is given by n = 182. - Robert FERREOL, Apr 03 2024