cp's OEIS Frontend

Fractions: 1,1,15/2,21/5,10,33/7,1365/4,1/3,102,...

Second bisection is A146535(n+2).

Row products of A138243. - Mats Granvik, Mar 08 2008

From Gary W. Adamson, Aug 09 2008: (Start)

Equals row products of triangle A143343 and for a(n) > 1, row products of triangle A080092.

Julius Worpitzky's 1883 algorithm for generating Bernoulli numbers is described in A028246. (End)

The sequence of denominators of B_n is defined here by convention, not by necessity. The convention amounts to mapping 0 to the rational number 0/1. It might be more appropriate to regard numerators and denominators of the Bernoulli numbers as independent sequences N_n and D_n which combine to B_n = N_n / D_n. This is suggested by the theorem of Clausen which describes the denominators as the sequence D_n = 1, 2, 6, 2, 30, 2, 42, ... which combines with N_n = 1, -1, 1, 0, -1, 0, ... to the sequence of Bernoulli numbers. (Cf. A141056 and A027760.) - Peter Luschny, Apr 29 2009

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

Inverse Gudermannian gd^(-1)(x) = log(sec(x) + tan(x)) = log(tan(Pi/4 + x/2)) = arctanh(sin(x)) = 2 * arctanh(tan(x/2)) = 2 * arctanh(csc(x) - cot(x)). - Michael Somos, Mar 19 2011

a(n) is the number of downup permutations of [2n]. Example: a(2)=5 counts 4231, 4132, 3241, 3142, 2143. - David Callan, Nov 21 2011

a(n) is the number of increasing full binary trees on vertices {0,1,2,...,2n} for which the leftmost leaf is labeled 2n. - David Callan, Nov 21 2011

a(n) is the number of unordered increasing trees of size 2n+1 with only even degrees allowed and degree-weight generating function given by cosh(t). - Markus Kuba, Sep 13 2014

a(n) is the number of standard Young tableaux of skew shape (n+1,n,n-1,...,3,2)/(n-1,n-2,...2,1). - Ran Pan, Apr 10 2015

Since cos(z) has a root at z = Pi/2 and no other root in C with a smaller |z|, the radius of convergence of the e.g.f. (intended complex-valued) is Pi/2 = A019669 (see also A028296). - Stanislav Sykora, Oct 07 2016

All terms are odd. - Alois P. Heinz, Jul 22 2018

The sequence starting with a(1) is periodic modulo any odd prime p. The minimal period is (p-1)/2 if p == 1 mod 4 and p-1 if p == 3 mod 4 [Knuth & Buckholtz, 1967, Theorem 2]. - Allen Stenger, Aug 03 2020

Conjecture: taking the sequence [a(n) : n >= 1] modulo an integer k gives a purely periodic sequence with period dividing phi(k). For example, the sequence taken modulo 21 begins [1, 5, 19, 20, 16, 2, 1, 5, 19, 20, 16, 2, 1, 5, 19, 20, 16, 2, 1, 5, 19, ...] with an apparent period of 6 = phi(21)/2. - Peter Bala, May 08 2023

a(n)/A027642(n) (Bernoulli numbers) provide the a-sequence for the Sheffer matrix A094816 (coefficients of orthogonal Poisson-Charlier polynomials). See the W. Lang link under A006232 for a- and z-sequences for Sheffer matrices. The corresponding z-sequence is given by the rationals A130189(n)/A130190(n).

Harvey (2008) describes a new algorithm for computing Bernoulli numbers. His method is to compute B(k) modulo p for many small primes p and then reconstruct B(k) via the Chinese Remainder Theorem. The time complexity is O(k^2 log(k)^(2+eps)). The algorithm is especially well-suited to parallelization. - Jonathan Vos Post, Jul 09 2008

Regard the Bernoulli numbers as forming a vector = B_n, and the variant starting (1, 1/2, 1/6, 0, -1/30, ...), (i.e., the first 1/2 has sign +) as forming a vector Bv_n. The relationship between the Pascal triangle matrix, B_n, and Bv_n is as follows: The binomial transform of B_n = Bv_n. B_n is unchanged when multiplied by the Pascal matrix with rows signed (+-+-, ...), i.e., (1; -1,-1; 1,2,1; ...). Bv_n is unchanged when multiplied by the Pascal matrix with columns signed (+-+-, ...), i.e., (1; 1,-1; 1,-2,1; 1,-3,3,-1; ...). - Gary W. Adamson, Jun 29 2012

The sequence of the Bernoulli numbers B_n = a(n)/A027642(n) is the inverse binomial transform of the sequence {A164555(n)/A027642(n)}, illustrated by the fact that they appear as top row and left column in A190339. - Paul Curtz, May 13 2016

Named by de Moivre (1773; "the numbers of Mr. James Bernoulli") after the Swiss mathematician Jacob Bernoulli (1655-1705). - Amiram Eldar, Oct 02 2023

Number of Joyce trees with 2n-1 nodes. Number of tremolo permutations of {0,1,...,2n}. - Ralf Stephan, Mar 28 2003

The Hankel transform of this sequence is A000178(n) for n odd = 1, 12, 34560, ...; example: det([1, 2, 16; 2, 16, 272, 16, 272, 7936]) = 34560. - Philippe Deléham, Mar 07 2004

a(n) is the number of increasing labeled full binary trees with 2n-1 vertices. Full binary means every non-leaf vertex has two children, distinguished as left and right; labeled means the vertices are labeled 1,2,...,2n-1; increasing means every child has a label greater than its parent. - David Callan, Nov 29 2007

From Micha Hofri (hofri(AT)wpi.edu), May 27 2009: (Start)

a(n) was found to be the number of permutations of [2n] which when inserted in order, to form a binary search tree, yield the maximally full possible tree (with only one single-child node).

The e.g.f. is sec^2(x)=1+tan^2(x), and the same coefficients can be manufactured from the tan(x) itself, which is the e.g.f. for the number of trees as above for odd number of nodes. (End)

a(n) is the number of increasing strict binary trees with 2n-1 nodes. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 07 2014

For relations to alternating permutations, Euler and Bernoulli polynomials, zigzag numbers, trigonometric functions, Fourier transform of a square wave, quantum algebras, and integrals over and in n-dimensional hypercubes and over Green functions, see Hodges and Sukumar. For further discussion on the quantum algebra, see the later Hodges and Sukumar reference and the paper by Hetyei presenting connections to the general combinatorial theory of Viennot on orthogonal polynomials, inverse polynomials, tridiagonal matrices, and lattice paths (thereby related to continued fractions and cumulants). - Tom Copeland, Nov 30 2014

The Zigzag Hankel transform is A000178. That is, A000178(2*n - k) = det( [a(i+j - k)]{i,j = 1..n} ) for n>0 and k=0,1. - _Michael Somos, Mar 12 2015

a(n) is the number of standard Young tableaux of skew shape (n,n,n-1,n-2,...,3,2)/(n-1,n-2,n-3,...,2,1). - Ran Pan, Apr 10 2015

For relations to the Sheffer Appell operator calculus and a Riccati differential equation for generating the Meixner-Pollaczek and Krawtchouk orthogonal polynomials, see page 45 of the Feinsilver link and Rzadkowski. - Tom Copeland, Sep 28 2015

For relations to an elliptic curve, a Weierstrass elliptic function, the Lorentz formal group law, a Lie infinitesimal generator, and the Eulerian numbers A008292, see A155585. - Tom Copeland, Sep 30 2015

Absolute values of the alternating sums of the odd-numbered rows (where the single 1 at the apex of the triangle is counted as row #1) of the Eulerian triangle, A008292. The actual alternating sums alternate in sign, e.g., 1, -2, 16, -272, etc. (Even-numbered rows have alternating sums always 0.) - Gregory Gerard Wojnar, Sep 28 2018

The sequence is periodic modulo any odd prime p. The minimal period is (p-1)/2 if p == 1 mod 4 and p-1 if p == 3 mod 4 [Knuth & Buckholtz, 1967, Theorem 1]. - Allen Stenger, Aug 03 2020

From Peter Bala, Dec 24 2021: (Start)

Conjectures:

1) The sequence taken modulo any integer k eventually becomes periodic with period dividing phi(k).

2) The Gauss congruences a(n*p^k) == a(n*p^(k-1)) ( mod p^k ) hold for all prime p and positive integers n and k, except when p = 2, n = 1 and k = 1 or 2.

3) For i >= 1 define a_i(n) = a(n+i). The Gauss congruences a_i(n*p^k) == a_i(n*p^(k-1)) ( mod p^k ) hold for all prime p and positive integers n and k. If true, then for each i >= 1 the expansion of exp(Sum_{n >= 1} a_i(n)*x^n/n) has integer coefficients. For an example, see A262145.(End)

Let M = n X n matrix with (i,j)-th entry a(n+1-j, n+1-i), e.g., if n = 3, M = [1 1 1; 3 1 0; 2 0 0]. Given a sequence s = [s(0)..s(n-1)], let b = [b(0)..b(n-1)] be its inverse binomial transform and let c = [c(0)..c(n-1)] = M^(-1)*transpose(b). Then s(k) = Sum_{i=0..n-1} b(i)*binomial(k,i) = Sum_{i=0..n-1} c(i)*k^i, k=0..n-1. - Gary W. Adamson, Nov 11 2001

From Gary W. Adamson, Aug 09 2008: (Start)

Julius Worpitzky's 1883 algorithm generates Bernoulli numbers.

By way of example [Wikipedia]:

B0 = 1;

B1 = 1/1 - 1/2;

B2 = 1/1 - 3/2 + 2/3;

B3 = 1/1 - 7/2 + 12/3 - 6/4;

B4 = 1/1 - 15/2 + 50/3 - 60/4 + 24/5;

B5 = 1/1 - 31/2 + 180/3 - 390/4 + 360/5 - 120/6;

B6 = 1/1 - 63/2 + 602/3 - 2100/4 + 3360/5 - 2520/6 + 720/7;

...

Note that in this algorithm, odd n's for the Bernoulli numbers sum to 0, not 1, and the sum for B1 = 1/2 = (1/1 - 1/2). B3 = 0 = (1 - 7/2 + 13/3 - 6/4) = 0. The summation for B4 = -1/30. (End)

Pursuant to Worpitzky's algorithm and given M = A028246 as an infinite lower triangular matrix, M * [1/1, -1/2, 1/3, ...] (i.e., the Harmonic series with alternate signs) = the Bernoulli numbers starting [1/1, 1/2, 1/6, ...]. - Gary W. Adamson, Mar 22 2012

From Tom Copeland, Oct 23 2008: (Start)

G(x,t) = 1/(1 + (1-exp(x*t))/t) = 1 + 1 x + (2 + t)*x^2/2! + (6 + 6t + t^2)*x^3/3! + ... gives row polynomials for A090582, the f-polynomials for the permutohedra (see A019538).

G(x,t-1) = 1 + 1*x + (1 + t)*x^2 / 2! + (1 + 4t + t^2)*x^3 / 3! + ... gives row polynomials for A008292, the h-polynomials for permutohedra.

G[(t+1)x,-1/(t+1)] = 1 + (1+ t) x + (1 + 3t + 2 t^2) x^2 / 2! + ... gives row polynomials for the present triangle. (End)

The Worpitzky triangle seems to be an apt name for this triangle. - Johannes W. Meijer, Jun 18 2009

If Pascal's triangle is written as a lower triangular matrix and multiplied by A028246 written as an upper triangular matrix, the product is a matrix where the (i,j)-th term is (i+1)^j. For example,

1,0,0,0 1,1,1, 1 1,1, 1, 1

1,1,0,0 * 0,1,3, 7 = 1,2, 4, 8

1,2,1,0 0,0,2,12 1,3, 9,27

1,3,3,1 0,0,0, 6 1,4,16,64

So, numbering all three matrices' rows and columns starting at 0, the (i,j) term of the product is (i+1)^j. - Jack A. Cohen (ProfCohen(AT)comcast.net), Aug 03 2010

The Fi1 and Fi2 triangle sums are both given by sequence A000670. For the definition of these triangle sums see A180662. The mirror image of the Worpitzky triangle is A130850. - Johannes W. Meijer, Apr 20 2011

Let S_n(m) = 1^m + 2^m + ... + n^m. Then, for n >= 0, we have the following representation of S_n(m) as a linear combination of the binomial coefficients:

S_n(m) = Sum_{i=1..n+1} a(i+n*(n+1)/2)*C(m,i). E.g., S_2(m) = a(4)*C(m,1) + a(5)*C(m,2) + a(6)*C(m,3) = C(m,1) + 3*C(m,2) + 2*C(m,3). - Vladimir Shevelev, Dec 21 2011

Given the set X = [1..n] and 1 <= k <= n, then a(n,k) is the number of sets T of size k of subset S of X such that S is either empty or else contains 1 and another element of X and such that any two elemements of T are either comparable or disjoint. - Michael Somos, Apr 20 2013

Working with the row and column indexing starting at -1, a(n,k) gives the number of k-dimensional faces in the first barycentric subdivision of the standard n-dimensional simplex (apply Brenti and Welker, Lemma 2.1). For example, the barycentric subdivision of the 2-simplex (a triangle) has 1 empty face, 7 vertices, 12 edges and 6 triangular faces giving row 4 of this triangle as (1,7,12,6). Cf. A053440. - Peter Bala, Jul 14 2014

See A074909 and above g.f.s for associations among this array and the Bernoulli polynomials and their umbral compositional inverses. - Tom Copeland, Nov 14 2014

An e.g.f. G(x,t) = exp[P(.,t)x] = 1/t - 1/[t+(1-t)(1-e^(-xt^2))] = (1-t) * x + (-2t + 3t^2 - t^3) * x^2/2! + (6t^2 - 12t^3 + 7t^4 - t^5) * x^3/3! + ... for the shifted, reverse, signed polynomials with the first element nulled, is generated by the infinitesimal generator g(u,t)d/du = [(1-u*t)(1-(1+u)t)]d/du, i.e., exp[x * g(u,t)d/du] u eval. at u=0 generates the polynomials. See A019538 and the G. Rzadkowski link below for connections to the Bernoulli and Eulerian numbers, a Ricatti differential equation, and a soliton solution to the KdV equation. The inverse in x of this e.g.f. is Ginv(x,t) = (-1/t^2)*log{[1-t(1+x)]/[(1-t)(1-tx)]} = [1/(1-t)]x + [(2t-t^2)/(1-t)^2]x^2/2 + [(3t^2-3t^3+t^4)/(1-t)^3]x^3/3 + [(4t^3-6t^4+4t^5-t^6)/(1-t)^4]x^4/4 + ... . The numerators are signed, shifted A135278 (reversed A074909), and the rational functions are the columns of A074909. Also, dG(x,t)/dx = g(G(x,t),t) (cf. A145271). (Analytic G(x,t) added, and Ginv corrected and expanded on Dec 28 2015.) - Tom Copeland, Nov 21 2014

The operator R = x + (1 + t) + t e^{-D} / [1 + t(1-e^(-D))] = x + (1+t) + t - (t+t^2) D + (t+3t^2+2t^3) D^2/2! - ... contains an e.g.f. of the reverse row polynomials of the present triangle, i.e., A123125 * A007318 (with row and column offset 1 and 1). Umbrally, R^n 1 = q_n(x;t) = (q.(0;t)+x)^n, with q_m(0;t) = (t+1)^(m+1) - t^(m+1), the row polynomials of A074909, and D = d/dx. In other words, R generates the Appell polynomials associated with the base sequence A074909. For example, R 1 = q_1(x;t) = (q.(0;t)+x) = q_1(0;t) + q__0(0;t)x = (1+2t) + x, and R^2 1 = q_2(x;t) = (q.(0;t)+x)^2 = q_2(0:t) + 2q_1(0;t)x + q_0(0;t)x^2 = 1+3t+3t^2 + 2(1+2t)x + x^2. Evaluating the polynomials at x=0 regenerates the base sequence. With a simple sign change in R, R generates the Appell polynomials associated with A248727. - Tom Copeland, Jan 23 2015

For a natural refinement of this array, see A263634. - Tom Copeland, Nov 06 2015

From Wolfdieter Lang, Mar 13 2017: (Start)

The e.g.f. E(n, x) for {S(n, m)}{m>=0} with S(n, m) = Sum{k=1..m} k^n, n >= 0, (with undefined sum put to 0) is exp(x)*R(n+1, x) with the exponential row polynomials R(n, x) = Sum_{k=1..n} a(n, k)*x^k/k!. E.g., e.g.f. for n = 2, A000330: exp(x)*(1*x/1!+3*x^2/2!+2*x^3/3!).

The o.g.f. G(n, x) for {S(n, m)}{m >=0} is then found by Laplace transform to be G(n, 1/p) = p*Sum{k=1..n} a(n+1, k)/(p-1)^(2+k).

Hence G(n, x) = x/(1 - x)^(n+2)*Sum_{k=1..n} A008292(n,k)*x^(k-1).

E.g., n=2: G(2, 1/p) = p*(1/(p-1)^2 + 3/(p-1)^3 + 2/(p-1)^4) = p^2*(1+p)/(p-1)^4; hence G(2, x) = x*(1+x)/(1-x)^4.

This works also backwards: from the o.g.f. to the e.g.f. of {S(n, m)}_{m>=0}. (End)

a(n,k) is the number of k-tuples of pairwise disjoint and nonempty subsets of a set of size n. - Dorian Guyot, May 21 2019

From Rajesh Kumar Mohapatra, Mar 16 2020: (Start)

a(n-1,k) is the number of chains of length k in a partially ordered set formed from subsets of an n-element set ordered by inclusion such that the first term of the chains is either the empty set or an n-element set.

Also, a(n-1,k) is the number of distinct k-level rooted fuzzy subsets of an n-set ordered by set inclusion. (End)

The relations on p. 34 of Hasan (also p. 17 of Franco and Hasan) agree with the relation between A019538 and this entry given in the formula section. - Tom Copeland, May 14 2020

T(n,k) is the size of the Green's L-classes in the D-classes of rank (k-1) in the semigroup of partial transformations on an (n-1)-set. - Geoffrey Critzer, Jan 09 2023

T(n,k) is the number of strongly connected binary relations on [n] that have period k (A367948) and index 1. See Theorem 5.4.25(6) in Ki Hang Kim reference. - Geoffrey Critzer, Dec 07 2023