cp's OEIS Frontend

Meyers (see Guy reference) conjectures that for all r >= 1, the least odd number not in the set {a(i): i < prime(r)} is prime(r+1). - N. J. A. Sloane, Jan 08 2021

Meyers' conjecture would be refuted if and only if for some r there were such a large gap between prime(r) and prime(r+1) that there existed a composite c for which prime(r) < c < a(c) < prime(r+1), in which case (by Bertrand's postulate) c would necessarily be a term of A246281. - Antti Karttunen, Mar 29 2021

a(n) is odd for all n and for each odd m there exists a k with a(k) = m (see A064216). a(n) > n for n > 1: bijection between the odd and all numbers. - Reinhard Zumkeller, Sep 26 2001

a(n) and n have the same number of distinct primes with (A001222) and without multiplicity (A001221). - Michel Marcus, Jun 13 2014

From Antti Karttunen, Nov 01 2019: (Start)

More generally, a(n) has the same prime signature as n, A046523(a(n)) = A046523(n). Also A246277(a(n)) = A246277(n) and A287170(a(n)) = A287170(n).

Many permutations and other sequences that employ prime factorization of n to encode either polynomials, partitions (via Heinz numbers) or multisets in general can be easily defined by using this sequence as one of their constituent functions. See the last line in the Crossrefs section for examples.

(End)

Polynomial reduction: an introduction

...

We begin with an example. Suppose that p(x) is a polynomial, so that p(x)=(x^2)t(x)+r(x) for some polynomials t(x) and r(x), where r(x) has degree 0 or 1. Replace x^2 by x+1 to get (x+1)t(x)+r(x), which is (x^2)u(x)+v(x) for some u(x) and v(x), where v(x) has degree 0 or 1. Continuing in this manner results in a fixed polynomial w(x) of degree 0 or 1. If p(x)=x^n, then w(x)=x*F(n)+F(n-1), where F=A000045, the sequence of Fibonacci numbers.

In order to generalize, write d(g) for the degree of an arbitrary polynomial g(x), and suppose that p, q, s are polynomials satisfying d(s)s in this manner until reaching w such that d(w)s.

The coefficients of (reduction of p by q->s) comprise a vector of length d(q)-1, so that a sequence p(n,x) of polynomials begets a sequence of vectors, such as (F(n), F(n-1)) in the above example. We are interested in the component sequences (e.g., F(n-1) and F(n)) for various choices of p(n,x).

Following are examples of reduction by x^2->x+1:

n-th Fibonacci p(x) -> A192232+x*A112576

n-th cyclotomic p(x) -> A192233+x*A051258

n-th 1st-kind Chebyshev p(x) -> A192234+x*A071101

n-th 2nd-kind Chebyshev p(x) -> A192235+x*A192236

x(x+1)(x+2)...(x+n-1) -> A192238+x*A192239

(x+1)^n -> A001519+x*A001906

(x^2+x+1)^n -> A154626+x*A087635

(x+2)^n -> A020876+x*A030191

(x+3)^n -> A192240+x*A099453

...

Suppose that b=(b(0), b(1),...) is a sequence, and let p(n,x)=b(0)+b(1)x+b(2)x^2+...+b(n)x^n. We define (reduction of sequence b by q->s) to be the vector given by (reduction of p(n,x) by q->s), with components in the order of powers, from 0 up to d(q)-1. For k=0,1,...,d(q)-1, we then have the "k-sequence of (reduction of sequence b by q->s)". Continuing the example, if b is the sequence given by b(k)=1 if k=n and b(k)=0 otherwise, then the 0-sequence of (reduction of b by x^2->x+1) is (F(n-1)), and the 1-sequence is (F(n)).

...

For selected sequences b, here are the 0-sequences and 1-sequences of (reduction of b by x^2->x+1):

b=A000045, Fibonacci sequence (1,1,2,3,5,8,...) yields

0-sequence A166536 and 1-sequence A064831.

b=(1,A000045)=(1,1,1,2,3,5,8,...) yields

0-sequence A166516 and 1-sequence A001654.

b=A000027, natural number sequence (1,2,3,4,...) yields

0-sequence A190062 and 1-sequence A122491.

b=A000032, Lucas sequence (1,3,4,7,11,...) yields

0-sequence A192243 and 1-sequence A192068.

b=A000217, triangular sequence (1,3,6,10,...) yields

0-sequence A192244 and 1-sequence A192245.

b=A000290, squares sequence (1,4,9,16,...) yields

0-sequence A192254 and 1-sequence A192255.

More examples: A192245-A192257.

...

More comments:

(1) If s(n,x)=(reduction of x^n by q->s) and

p(x)=p(0)x^n+p(1)x^(n-1)+...+p(n)x^0, then

(reduction of p by q->s)=p(0)s(n,x)+p(1)s(n-1,x)

+...+p(n-1)s(1,x)+p(n)s(0,x). See A192744.

(2) For any polynomial p(x), let P(x)=(reduction of p(x)

by q->s). Then P(r)=p(r) for each zero r of

q(x)-s(x). In particular, if q(x)=x^2 and s(x)=x+1,

then P(r)=p(r) if r=(1+sqrt(5))/2 (golden ratio) or

r=(1-sqrt(5))/2.

The original motivation for this sequence was to encode the prime factorization of n in the binary representation of a(n), each such representation being unique as long as this map is restricted to A005117 (squarefree numbers, resulting a permutation of nonnegative integers A048672) or any of its subsequence, resulting an injective function like A048623 and A048639.

However, also the restriction to A260443 (not all terms of which are squarefree) results a permutation of nonnegative integers, namely A001477, the identity permutation.

When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443), then a(n) gives the evaluation of that polynomial at x=2.

The primitive completely additive integer sequence that satisfies a(n) = a(A225546(n)), n >= 1. By primitive, we mean that if b is another such sequence, then there is an integer k such that b(n) = k * a(n) for all n >= 1. - Peter Munn, Feb 03 2020

If the binary rank of an integer partition y is given by Sum_i 2^(y_i-1), and the Heinz number is Product_i prime(y_i), then a(n) is the binary rank of the integer partition with Heinz number n. Note the function taking a set s to Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices), and the function taking a multiset m to Product_i prime(m_i) is the inverse of A112798 (prime indices). - Gus Wiseman, May 22 2024

The exponents in the prime factorization of term a(n) give the coefficients of the n-th Stern polynomial. See A125184 and the examples.

None of the terms have prime gaps in their factorization, i.e., all can be found in A073491.

Contains neither perfect squares nor prime powers with exponent > 1. A277701 gives the positions of the terms that are 2*square. - Antti Karttunen, Oct 27 2016

Many of the derived sequences (like A002487) have similar "Fir forest" or "Gaudian cathedrals" style scatter plot. - Antti Karttunen, Mar 21 2017

The binary digits of a(n) encode the prime factorization of A007913(n), where the i-th digit from the right is 1 if and only if prime(i) divides A007913(n), otherwise 0. - Robert Israel, Jan 12 2015

Old name: a(1) = 0; a(A000040(n)) = 2^(n-1), and a(n*m) = a(n) XOR a(m).

XOR is the bitwise exclusive or operation (A003987).

a(k^2) = 0 for a natural number k.

Equivalently, the i-th binary digit from the right is 1 iff prime(i) divides n an odd number of times, otherwise zero. - Ethan Beihl, Oct 15 2016

When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443, with scheme explained in A206284), then A048675(n) gives the evaluation of that polynomial at x=2. This sequence is otherwise similar, except the polynomial is evaluated over the field GF(2), which implies also that all its coefficients are essentially reduced modulo 2. - Antti Karttunen, Dec 11 2015

Squarefree numbers (A005117) give the positions k where a(k) = A048675(k). - Antti Karttunen, Oct 29 2016

From Peter Munn, Jun 07 2021: (Start)

When we encode polynomials with nonnegative integer coefficients as described by Antti Karttunen above, polynomial addition is represented by integer multiplication, multiplication is represented by A297845(.,.), and this sequence represents a surjective semiring homomorphism to polynomials in GF(2)[x] (encoded as described in A048720). The mapping of addition operations by this homomorphism is part of the sequence definition: "a(n*m) = a(n) XOR a(m)". The mapping of multiplication is given by a(A297845(n, k)) = A048720(a(n), a(k)).

In a related way, A329329 defines a representation of a different set of polynomials as positive integers, namely polynomials in GF(2)[x,y].

Let P_n(x,y) denote the polynomial represented, as in A329329, by n >= 1. If 0 is substituted for y in P_n(x,y), we get a polynomial P'_n(x,y) (in which y does not appear, of course) that is equivalent to a polynomial P'_n(x) in GF(2)[x]. a(n) is the integer encoding of P'_n(x) (described in A048720).

Viewed as above, this sequence represents another surjective homomorphism, a homomorphism between polynomial rings, with A329329(.,.)/A059897(.,.) and A048720(.,.)/A003987(.,.) as the respective ring operations.

a(n) can be composed as a(n) = A048675(A007913(n)) and the effect of the A007913(.) component corresponds to different operations on the respective polynomial domains of the two homomorphisms described above. In the first homomorphism, coefficients are reduced modulo 2; in the second, 0 is substituted for y. This is illustrated in the examples.

(End)

Starting with 1, which encodes 0-polynomial, each integer m encodes (or "matches") a polynomial p(m,x) with nonnegative integer coefficients determined by the prime factorization of m. Write m = prime(1)^e(1) * prime(2)^e(2) * ... * prime(k)^e(k); then p(m,x) = e(1) + e(2)x + e(3)x^2 + ... + e(k)x^k.

Identities:

p(m*n,x) = p(m,x) + p(n,x),

p(m*n,x) = p(gcd(m,n),x) + p(lcm(m,n),x),

p(m+n,x) = p(gcd(m,n),x) + p((m+n)/gcd(m,n),x), so that if A003057 is read as a square matrix, then

p(A003057,x) = p(A003989,x) + p(A106448,x).

Apart from powers of 3, all terms are even. - Charles R Greathouse IV, Feb 11 2012

Contains 2*p^m and p*2^m if p is an odd prime and m is in A052485. - Robert Israel, Oct 09 2016

Additive with a(p^e) = e * (PrimePi(p)!), where PrimePi(n) = A000720(n).

a(3181) has 1001 decimal digits. - Michael De Vlieger, Dec 24 2017

Replace "3" with "x" and extend the definition of a to positive rationals and a becomes an isomorphism between positive rationals under multiplication and polynomials over Z under addition. This remark generalizes A001222, A048675 and A054841: evaluate said polynomial at x=1, x=2 and x=10, respectively.

For examples of such evaluations at x=3, see "Other identities" in the Formula section. - Antti Karttunen, Jul 31 2015

From Antti Karttunen, Jul 29 2015: (Start)

The square array A(row,col) is read by downwards antidiagonals as: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

A(n,m) (entry at row=n, column=m) gives the evaluation at x=n of the polynomial (with nonnegative integer coefficients) bijectively encoded in the prime factorization of m. See A206284, A206296 for the details of that encoding. (The roles of variables n and m were accidentally swapped in this description, corrected by Antti Karttunen, Oct 30 2016)

(End)

Each row is a completely additive sequence, row n mapping prime(m) to n^(m-1). - Peter Munn, Apr 22 2022