cp's OEIS Frontend

n*a(n) is the number of complex multiplications needed for the fast Fourier transform of n numbers, writing n = r1 * r2 where r1 is a prime.

This sequence with offset 1 and a(1) = 0 is completely additive with a(p^e) = e*(p-1) for prime p and e >= 0. - Werner Schulte, Feb 23 2019

From Antti Karttunen, Feb 09 2024: (Start)

Numbers k for which A276085(k) is a multiple of four.

Even terms in this sequence are all multiples of four.

A multiplicative semigroup; if m and n are in the sequence then so is m*n.

(End)

Appears to be products of an even number of terms from {4} U A065091 (counting repetitions). - Peter Munn, Jul 15 2024

a(n)=2 if and only if n-1 is in A079523. - Benoit Cloitre, Mar 10 2003

Partial sums modulo 4 of the sequence 1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), a(6), ... - Philippe Deléham, Mar 04 2004

To construct the sequence: start with 1 and concatenate 4 -1 = 3: 1, 3, then change the last term (2 -> 1, 3 ->2 ) gives 1, 2. Concatenate 1, 2 with 4 -1 = 3, 4 - 2 = 2: 1, 2, 3, 2 and change the last term: 1, 2, 3, 1. Concatenate 1, 2, 3, 1 with 4 - 1 = 3, 4 - 2 = 2, 4 - 3 = 1, 4 - 1 = 3: 1, 2, 3, 1, 3, 2, 1, 3 and change the last term: 1, 2, 3, 1, 3, 2, 1, 2 etc. - Philippe Deléham, Mar 04 2004

To construct the sequence: start with the Thue-Morse sequence A010060 = 0, 1, 1, 0, 1, 0, 0, 1, ... Then change 0 -> 1, 2, 3, and 1 -> 3, 2, 1, gives: 1, 2, 3, , 3, 2, 1, ,3, 2, 1, , 1, 2, 3, , 3, 2, 1, , ... and fill in the successive holes with the successive terms of the sequence itself. - _Philippe Deléham, Mar 04 2004

To construct the sequence: to insert the number 2 between the A003156(k)-th term and the (1 + A003156(k))-th term of the sequence 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, ... - Philippe Deléham, Mar 04 2004

Conjecture. The sequence is formed by the numbers of 1's between every pair of consecutive 2's in A076826. - Vladimir Shevelev, May 31 2009

The positive integers are partitioned between this sequence, A332821 and A332822, which list the integers in respective cosets of the subgroup.

As the sequence lists the integers in a multiplicative subgroup of the positive rationals, the sequence is closed under multiplication and, provided the result is an integer, under division.

It follows that for any n in this sequence, all powers n^k are present (k >= 0), as are all cubes.

If we take each odd term of this sequence and replace each prime in its factorization by the next smaller prime, the resulting numbers are a permutation of the full sequence; and if we take the square root of each square term we get the full sequence.

There are no primes in the sequence, therefore if k is present and p is a prime, k*p and k/p are absent (noting that k/p might not be an integer). This property extends from primes to all terms of A050376 (often called Fermi-Dirac primes), therefore to squares of primes, 4th powers of primes etc.

The terms are the even numbers in A332821 halved. The terms are also the numbers m such that 5m is in A332821, and so on for alternate primes: 11, 17, 23 etc. Likewise, the terms are the numbers m such that 3m is in A332822, and so on for alternate primes: 7, 13, 19 etc.

The numbers that are half of the even terms of this sequence are in A332822, which consists exactly of those numbers. The numbers that are one third of the terms that are multiples of 3 are in A332821, which consists exactly of those numbers. These properties extend in a pattern of alternating primes as described in the previous paragraph.

If k is an even number, exactly one of {k/2, k, 2k} is in the sequence (cf. A191257 / A067368 / A213258); and generally if k is a multiple of a prime p, exactly one of {k/p, k, k*p} is in the sequence.

If m and n are in this sequence then so is m*n (the definition of "multiplicative semigroup"), while if n is in this sequence, and x is in the complement A359830, then n*x is in A359830. This essentially follows from the fact that A048675 is totally additive sequence. Compare to A329609. - Antti Karttunen, Jan 17 2023

Completely additive modulo 3.

The equivalent sequence modulo 2 is A096268 (with offset 1), which produces the {A003159, A036554} classification.

Let H be the multiplicative subgroup of the positive rational numbers generated by the products of two consecutive primes and the cubes of primes. a(n) indicates the coset of H containing n. a(n) = 0 if n is in H. a(n) = 1 if n is in 2H. a(n) = -1 if n is in (1/2)H.

The properties of this classification can usefully be compared to two well-studied classifications. With the {A026424, A028260} classes, multiplying a member of one class by a prime gives a member of the other class. With the {A000028, A000379} classes, adding a factor to the Fermi-Dirac factorization of a member of one class gives a member of the other class. So, if 4 is not a Fermi-Dirac factor of k, k and 4k will be in different classes of the {A000028, A000379} set; but k and 4k will be in the same class of the {A026424, A028260} set. For two numbers to necessarily be in different classes when they differ in either of the 2 ways described above, 3 classes are needed.

With the classes defined by this sequence, no two of k, 2k and 4k are in the same class. This is a consequence of the following stronger property: if k is any positive integer and m is a member of A050376 (often called Fermi-Dirac primes), then no two of k, k * m, k * m^2 are in the same class. Also, if p and q are consecutive primes, then k * p and k * q are in different classes.

Further properties are given in the sequences that list the classes: A332820, A332821, A332822.

The scaled imaginary part of the Eisenstein integer-valued function, f, defined in A353445. - Peter Munn, Apr 27 2022

Values of k such that the Motzkin number A001006(k) is even. Values of k such that the number of restricted hexagonal polyominoes with k+1 cells (A002212) is even.

Or union of sequences {2*A079523(n)+k}, k=0,1. A generalization see in comment to A161639. - Vladimir Shevelev, Jun 15 2009

Or intersection of sequences A121539 and {A121539(n)-1}. A generalization see in comment to A161890. - Vladimir Shevelev, Jul 03 2009

Also numbers n for which A010060(n+2) = A010060(n). - Vladimir Shevelev, Jul 06 2009

The asymptotic density of this sequence is 1/3 (Rowland and Yassawi, 2015; Burns, 2016). - Amiram Eldar, Jan 30 2021

Numbers of the form 4^k*(2*n-1)-2 and 4^k*(2*n-1)-1 where n and k are positive integers. - Michael Somos, Oct 22 2021

Equivalently, increasing sequence defined by: "if k appears a*k+b does not", case a(1)=0, a=2, b=1.

Every even number ends with zero 1's and zero is even, so every even number is a term.

Consists of all even numbers together with A131323.

A035263(a(n)) = 1. - Reinhard Zumkeller, Mar 01 2012

For any number n > 0, let f(n) be the polynomial in a single indeterminate x where the coefficient of x^e is the prime(1+e)-adic valuation of n (where prime(k) denotes the k-th prime); f establishes a bijection between the positive numbers and the polynomials in a single indeterminate x with nonnegative integer coefficients; let g be the inverse of f; T(n, k) = g(f(n) * f(k)).

This table has many similarities with A248601.

For any n > 0 and m > 0, f(n * m) = f(n) + f(m).

Also, f(1) = 0 and f(2) = 1.

The function f can be naturally extended to the set of positive rational numbers: if r = u/v (not necessarily in reduced form), then f(r) = f(u) - f(v); as such, f is a homomorphism from the multiplicative group of positive rational numbers to the additive group of polynomials of a single indeterminate x with integer coefficients.

See A297473 for the main diagonal of T.

As a binary operation, T(.,.) is related to A306697(.,.) and A329329(.,.). When their operands are terms of A050376 (sometimes called Fermi-Dirac primes) the three operations give the same result. However the rest of the multiplication table for T(.,.) can be derived from these results because T(.,.) distributes over integer multiplication (A003991), whereas for A306697 and A329329, the equivalent derivation uses distribution over A059896(.,.) and A059897(.,.) respectively. - Peter Munn, Mar 25 2020

From Peter Munn, Jun 16 2021: (Start)

The operation defined by this sequence can be extended to be the multiplicative operator of a ring over the positive rationals that is isomorphic to the polynomial ring Z[x]. The extended function f (described in the author's original comments) is the isomorphism we use, and it has the same relationship with the extended operation that exists between their unextended equivalents.

Denoting this extension of T(.,.) as t_Q(.,.), we get t_Q(n, 1/k) = t_Q(1/n, k) = 1/T(n, k) and t_Q(1/n, 1/k) = T(n, k) for positive integers n and k. The result for other rationals is derived from the distributive property: t_Q(q, r*s) = t_Q(q, r) * t_Q(q, s); t_Q(q*r, s) = t_Q(q, s) * t_Q(r, s). This may look unusual because standard multiplication of rational numbers takes on the role of the ring's additive group.

There are many OEIS sequences that can be shown to be a list of the integers in an ideal of this ring. See the cross-references.

There are some completely additive sequences that similarly define by extension completely additive functions on the positive rationals that can be shown to be homomorphisms from this ring onto the integer ring Z, and these functions relate to some of the ideals. For example, the extended function of A048675, denoted A048675_Q, maps i/j to A048675(i) - A048675(j) for positive integers i and j. For any positive integer k, the set {r rational > 0 : k divides A048675_Q(r)} forms an ideal of the ring; for k=2 and k=3 the integers in this ideal are listed in A003159 and A332820 respectively.

(End)

It appears that the sequence can be calculated by any of the following methods:

(1) Start with 1 and repeatedly replace 1 with 1, 2, 1 and 2 with 1, 2, 2, 2, 1;

(2) a(1) = 1, all terms are either 1 or 2 and, for n > 0, a(n) = 1 if the length of the n-th run of 2's is 1; a(n) = 2 if the length of the n-th run of consecutive 2's is 3, with each run of 2's separated by a run of two 1's;

(3) replace each 3 in A080426 with 2. - John W. Layman, Feb 18 2003

Number of representations of n as a sum of Jacobsthal numbers (1 is allowed twice as a part). Partial sums are A003159. With interpolated zeros, g.f. is (Product_{k>=1} (1 + x^A078008(k)))/2. - Paul Barry, Dec 09 2004

In other words, the consecutive 0's or 1's in A010060 or A010059. - Robin D. Saunders (saunders_robin_d(AT)hotmail.com), Sep 06 2006

From Carlo Carminati, Feb 25 2011: (Start)

The sequence (starting with the second term) can also be calculated by the following method:

Apply repeatedly to the string S_0 = [2] the following algorithm: take a string S, double it, if the last figure is 1, just add the last figure to the previous one, if the last figure is greater than one, decrease it by one unit and concatenate a figure 1 at the end. (This algorithm is connected with the interpretation of the sequence as a continued fraction expansion.) (End)

This sequence, starting with the second term, happens to be the continued fraction expansion of the biggest cluster point of the set {x in [0,1]: F^k(x) >= x, for all k in N}, where F denotes the Farey map (see A187061). - Carlo Carminati, Feb 28 2011

Starting with the second term, the fixed point of the substitution 2 -> 211, 1 -> 2. - Carlo Carminati, Mar 03 2011

It appears that this sequence contains infinitely many distinct palindromic subsequences. - Alexander R. Povolotsky, Oct 30 2016

From Michel Dekking, Feb 13 2019: (Start)

Let tau defined by tau(0) = 01, tau(1) = 10 be the Thue-Morse morphism, with fixed point A010060. Consecutive runs in A010060 are 0, 11, 0, 1, 00, 1, 1, ..., which are coded by their lengths 1, 2, 1, 1, 2, ... Under tau^2 consecutive runs are mapped to consecutive runs:

tau^2(0) = 0110, tau^2(1) = 1001,

tau^2(00) = 01100110, tau^2(11) = 10011001.

The reason is that (by definition of a run!) runs of 0's and runs of 1's alternate in the sequence of runs, and this is inherited by the image of these runs under tau^2.

Under tau^2 the runs of length 1 are mapped to the sequence 1,2,1 of run lengths, and the runs of length 2 are mapped to the sequence 1,2,2,2,1 of run lengths. This proves John Layman's conjecture number (1): it follows that (a(n)) is fixed point of the morphism alpha

alpha: 1 -> 121, 2 -> 12221.

Since alpha(1) and alpha(2) are both palindromes, this also proves Alexander Povolotsky's conjecture.

(End)

Note that the first equation implies a(0)=0, so there is no need to specify an initial value.

Maximal cardinality of a double-free subset of {1, 2, ..., n}, or in other words, maximal size of a subset S of {1, 2, ..., n} with the property that if x is in S then 2x is not. a(0)=0 by convention.

Least k such that a(k)=n is equal to A003159(n).

To construct the sequence: let [a, b, c, a, a, a, b, c, a, b, c, ...] be the fixed point of the morphism a -> abc, b ->a, c -> a, starting from a(1) = a, then write the indices of a, b, c, that of a being written twice; see A092606. - Philippe Deléham, Apr 13 2004

Number of integers from {1,...,n} for which the subtraction of 1 changes the parity of the number of 1's in their binary expansion. - Vladimir Shevelev, Apr 15 2010

Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. - Vladimir Shevelev, Apr 16 2010

a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. Each number n appears A026465(n+1) times. - Philippe Deléham, Oct 19 2011

Another way of stating the last two comments from Philippe Deléham: the sequence can be obtained by replacing each term of the Thue-Morse sequence A010060 by the run number that term is in. - N. J. A. Sloane, Dec 31 2013