cp's OEIS Frontend

Closure under multiplication: if multiplication by m_1 carries totient values to totient values and multiplication by m_2 does also, then so does their composition, which is multiplication by m_1*m_2.

No odd terms are in the sequence except for 1.

32, 36, 40, 42, 48, 54, 64, and 72 are also in this sequence, although determining their position is difficult. - Charlie Neder, Aug 04 2019

From Jianing Song, Dec 12 2021: (Start)

Conjecture: defining this sequence as "positive integers m such that whenever n > 1 is in the range of the Euler totient function, so is m*n" would give the same terms. That is to say, it seems that if m is a nontotient number, then there exists a totient number n > 1 such that m*n is a nontotient.

The known primitive terms of this sequence (terms that are not products of two previous terms) are 1, 2, 6, 18, 20. More terms are needed to determine the primitive terms further. (End)

a(1) = 1 because the trivial group works.

If n > 1, then let G_n be a group of minimal order which has an irreducible complex representation of dimension n.

Since G_n has the n-dimensional and trivial representations, a_n = |G_n| >= n^2 + 1.

Since n divides the order of any finite group with an irreducible complex representation of dimension n, n divides a_n and this allows us to strengthen the lower bound to a_n >= n^2 + n.

An upper bound is given by a_n <= n*q_n, where q_n is the smallest positive integer which is a power of a prime and which is congruent to 1 mod n. This is because the group of affine transformations x --> a*x + b (from the finite field F_(q_n) to itself), where a^n = 1 and b is an arbitrary element of F_(q_n), has order n*q_n and an irreducible complex representation of dimension n.

The upper bound and the lower bound coincide if and only if (n > 1 and) n+1 is a power of a prime. This means that, for any such n, a(n) = n^2 + n.

Upper bound is n*A224503(n), for n > 1.

This function is sub-multiplicative: a(m*n) <= a(m)*a(n) because (any) G_m x G_n has an irreducible complex representation of dimension m*n.

(i) If n is an odd positive integer, then the number of Sylow 2-subgroups of the dihedral group of order 2n is n. Therefore all terms of this sequence are even.

(ii) Let p be a prime and let q be a power of p. The number of Sylow p-subgroups of PGL(2,q) is q+1.

(iii) Let q be a power of a prime and let r be a prime factor of q-1. Then the group of all affine transformations from the finite field F_q to itself has exactly q Sylow r-subgroups. This implies that q is a nonmember of the sequence, as long as q-1 has prime factors. Thus it works for all q except 2. (iv) The Third Sylow Theorem: If G is a finite group and p is a prime factor of |G|, then the number of Sylow p-subgroups of G is congruent to 1 mod p. 2 is in the sequence, since 2 is not congruent to 1 modulo any primes. It is never again this easy. Therefore we need an easier equivalent form of the membership criterion:

Easier Test. n > 2 is in this sequence iff the symmetric group S_n lacks a transitive subgroup with exactly n Sylow p-subgroups.

Proof. If S_n has a transitive subgroup with exactly n Sylow p-subgroups, then n trivially is a nonmember of this sequence.

For the other direction, suppose that G has exactly n Sylow p-subgroups. Then we will show that S_n has a transitive subgroup with exactly n Sylow p-subgroups. Let P be a Sylow p-subgroup of G and let N be its normalizer in G. Let G act on its Sylow p-subgroups by conjugation. This gives a homomorphism phi: G --> S_n. We want to show that phi(G) is also a group with exactly n Sylow p-subgroups. It is transitive by the Second Sylow Theorem.

First, phi(P) is a nontrivial subgroup of G: By properties of Sylow subgroups, P normalizes none of the other Sylow p-subgroups of G. Therefore phi(P) is a p-subgroup of G. Also, [phi(G):phi(P)] divides [G:P], which is a nonmultiple of p. Therefore phi(P) is a Sylow p-subgroup of phi(G). Since N normalizes P, phi(N) normalizes phi(P). Finally, nothing outside phi(N) can normalize phi(P), by the definition of phi.

Likewise phi(N) is a point-stabilizer in phi(G). Since phi(G) is a transitive subgroup of S_n, the index of phi(N) in phi(G) is n. Since phi(N) is the normalizer of phi(P) in phi(G), this means the number of Sylow p-subgroups of phi(G) is n and we are done.

We continue the notation used above with G, N and P in what follows. (For these comments, isolated examples are given that show different variations on the reasoning used to prove membership in this sequence.)

22 is in the sequence: If G is a finite group with exactly 22 Sylow p-subgroups, then p= 3 or 7. (Since there is no need to divide into cases based on the value of p, in what follows p= 3 or 7.) 22 has no proper divisors congruent to 1 mod p, so N is a maximal subgroup of G. Then the Easier Test can be strengthened to say "primitive" where it says "transitive". There are only 4 nonisomorphic primitive subgroups of S_22: M_22, Aut(M_22), A_22 and S_22. All of these have more than 22 Sylow p-subgroups.

34 is in the sequence: If G is a finite group with exactly 34 Sylow p-subgroups, then p= 3 or 11. 34 has no proper divisors congruent to 1 mod p and (proceeding as before) the only primitive subgroups of S_34 are S_34 and A_34. Both have more than 34 Sylow p-subgroups.

88 is a member: the only primitive permutation groups of degree 88 are S_88 and A_88. Neither of these has exactly 88 Sylow 29-subgroups and 88 has no proper divisors congruent to 1 mod 29. The divisors of 88 congruent to 1 mod 3 are 1, 4, 22 and 88. Then a minimal extension K of a Sylow 3-subgroup normalizer N must have [K:N]=4 (22 was already ruled out, as was 88 by the fact that S_88 and A_88 have more than 88 Sylow 3-subgroups). K will be maximal in G and have [G:K]=22. All of M_22, Aut(M_22), A_22 or S_22 have more than 88 Sylow 3-subgroups and G itself will have at least as many.

The way the sequence is defined, it is not obvious that it is computable.

The following condition is obviously computable and equivalent to the criterion for membership in this sequence: n is in the sequence iff it is true that a transitive subgroup of the symmetric group S_n is solvable iff it has a solvable point stabilizer.

As for the primes in the sequence, a theorem proved by Burnside guarantees that any unsolvable permutation group on a prime number of points is doubly transitive. The classification of doubly transitive permutation groups has been completed and it can be used to show that the only primes not in this sequence are 7, 13 and the Fermat primes larger than 3. So assuming the standard conjecture that 65537 is the largest Fermat prime, all primes except for these six (5, 7, 13, 17, 257 and 65537) are in this sequence.

If q (not equal to 2 or 3) is a power of a prime, then q+1 is not in this sequence, since PGL(2,q) is an unsolvable group with a solvable subgroup of index q+1 (isomorphic to the general affine group GA(1,q)).

Finally, if n is a nonmember of this sequence, then so is any multiple of n:

Since n is a nonmember of this sequence, there is a group G such that G is unsolvable and G has a solvable subgroup H of index n. Suppose N=d*n is a multiple of n. Then G x C_d (here C_d denotes a cyclic group of order d) is a group which is unsolvable because G is unsolvable. Nevertheless, it has a subgroup of index N isomorphic to H, which is solvable: this is the H x 1 subgroup.

This also means that any divisor of a member of this sequence is in this sequence and this form of the above-proved property is useful in proving membership in the sequence. One nice application of this form of that property is the following:

If n is insipid (that is, n is in A102842) and n/p is in this sequence for all primes p dividing n, then n is in this sequence.

Proof. Since n is insipid, n=1,2,3 or 4 or n>=34. If n=1,2,3 or 4, this is trivial since all of those values of n are in this sequence.

If n>=34, then let G be a group and let H be a solvable subgroup of index n in G.

Claim. H is not maximal in G.

Proof of Claim. Suppose H is maximal in G. Then let N be the core of H in G. G/N is isomorphic to a primitive permutation group on n points. Since n is insipid, this means G/N ~= A_n or S_n. Then restricting the quotient map (the map from G to G/N) to H yields a surjective homomorphism from H to a point stabilizer in S_n or A_n. This point stabilizer is isomorphic to S_(n-1) or A_(n-1). Since n>=34, n-1 >= 33 >= 5 so this image of H under this homomorphism is unsolvable and therefore H is unsolvable for a contradiction. The Claim is proved.

Since H is not maximal in G, there is a subgroup K of G such that G is properly contained in G and properly contains H. Then, by Lagrange's Theorem, [G:K] and [K:H] are proper divisors of n. This means there are (not necessarily distinct) prime factors p,q of n such that [G:K] | n/p and [K:H] | n/q. By our assumption, n/p and n/q are in this sequence. Then the property proved earlier implies that [G:K] and [K:H] are in this sequence. This means that the solvability of H implies the solvability of K, which, in turn, implies the solvability of G and the membership of n in this sequence. The proof is now complete.

A few basic properties: No prime p > 3 is in this sequence, since the subgroup of S_p generated by any p-cycle is primitive (and too small to be A_p or S_p when p>3).

It seems hard to find long gaps in this sequence. It seems plausible (this is implied by some conjectures in number theory) that there are infinitely many strings of 5 consecutive positive integers not in this sequence; however, I do not know of a construction which should yield infinitely many strings of 6 consecutive positive integers which are in the sequence (this may be just a reflection of my ignorance of the right families of finite groups); the largest example I know of a string of more than 5 consecutive integers not in this sequence has length 7 and first term 2^150-5.

If q is a power of a prime and d > 1 is a positive integer (except in the cases where d=2 and q <= 4, in which this construction yields symmetric or alternating groups), then (q^d-1)/(q-1) is not insipid for the following reason:

The group PGL(d,q) acts doubly transitively (and therefore primitively) on the (q^d-1)/(q-1) 1-dimensional subspaces of a d-dimensional vector space over the finite field of order q. In particular, when d=2, this number is q+1 and this is why each power of a prime (including the primes themselves) prevents the next positive integer from being insipid, in addition to being noninsipid itself. This is why the explanation for why 38 is noninsipid just said that 38=37+1.

The Magma code generates the insipid numbers <= U, with the exceptions of 1 and 2. Since I do not know Magma well enough to judge this for myself, it is possible that U has to be a constant (and not just another program variable) for this code to work properly.

This is the set of n such that n = 1 or 2 and A000019(n)=2.

The link gives all the insipid numbers < 1000, except for 1 and 2. - David L. Harden, Aug 15 2007

There are infinitely many insipid numbers. In fact, they are of density 1, because P. J. Cameron, P. M. Neumann and D. N. Teague proved that the number of non-insipid numbers less than n grows like 2n/log(n). - Sébastien Palcoux, Jul 23 2019

At order 24, the two groups which achieve the maximum derived length are S_4 and SL(2,3). At order 48, a group which achieves the maximum derived length is GL(2,3). At order 432, the only group which achieves the maximum derived length is 3^2:GL(2,3).

There are three groups of order 1296 achieving maximal derived length. - Charles R Greathouse IV, May 26 2014

The Maple code uses a recurrence for this function.

Here is a faster algorithm for computing members of this sequence. Input: a positive integer, n.

Step 1. Write n in base 4. This yields a string of digits. Each digit is 0, 1, 2 or 3.

Step 2. Make a pass through the string and replace every occurrence of "12" with "6". Now the string is a string of 0's, 1's, 2s, 3s and 6s.

Step 3. Make a pass through the string and replace every occurrence of "21" by "9". Now the string is a string of 0's, 1's, 2s 3s, 6s and 9s.

Step 4. Add the digits of the string. Call this sum S.

Step 5. Compute the product of f(d) over all digits d of the string, where f(0)=1 and f(d)= A099732(d) for d>0. As a table, these values are f(0)=1, f(1)=1, f(2)=2, f(3)=6, f(6)=72 and f(9)=1296. Call this product P.

Step 6. A099732(n)= P * 24^((n-S)/3).

Examples. n=412089:

Step 1. n = 1210212321 in base 4. Step 2. The new string is 61062321. Step 3. The new string is 6106239. Step 4. S = 6+1+0+6+2+3+9= 27. Step 5. P = 72*1*1*72*2*6*1296=80621568. Step 6. A099732(412089)=80621568 * 24^((412089-27)/3) = 80621568 * 24^(412062/3) = 80621568 * 24^137354.

n=25: Step 1. n=121 in base 4. Step 2. The new string is 61. Step 3. The new string is still 61, since there are no "21"s in 61. Step 4. S= 6+1 =7. Step 5. P= 72*1 = 72. Step 6. A099732(25) = 72 * 24^((25-7)/3) = 72 * 24^6.

n=37: Step 1. n=211 in base 4. Step 2. The new string is still 211, since there are no "12"s in "211". Step 3. The new string is 91. Step 4. S= 9+1 = 10. Step 5. P= 1296*1 = 1296. Step 6. A099732(37) = 1296 * 24^((37-10)/3) = 1296 * 24^9.

It is important that Step 2 be done before Step 3; indeed, proving that doing any of Step 3 before all of Step 2 is accomplished cannot result in a larger value (though it can result in a smaller value, or the same value if there are no "12"-"21" conflicts) is part of the proof of the correctness of this algorithm.

It is strange that each term of this sequence has, among its quadratic residues, only one more of -1,2,3,5,7,11... and thus gets into the sequence by 'doing the bare minimum' and not having the next term of that sequence as a quadratic residue also. For example, the quadratic residues modulo 73 include -1, 2 and 3 but not 5. With 241, 5 is a quadratic residue but 7 is not. With 1009, 7 is but 11 is not. This should stop at some point, but my computations haven't reached there yet (they have not been assisted electronically).

If someone wants to code up a program to compute members of this sequence quickly, one should strike a balance (if not using a totally different or much smarter approach) between using the sieve you can get by using the law of quadratic reciprocity (and the (-1/p) and (2/p) theorems) and using brute force to find primes with the right quadratic residues by chance.

For example, there are 2*3*5*6*8*9*11*14=1995840 residue classes modulo 8*3*5*7*11*13*17*19*23*29 containing odd primes with -1 and the primes up to 29 as quadratic residues. Simply enumerating these is significant work for a computer.

On the other hand, generating a smaller list of residue classes (for example, the 12960 residue classes modulo 8*3*5*7*11*13*17*19 which contain odd primes having -1 and the primes up to 19 as quadratic residues) and then leaving to chance (and brute force) the primality of p and that (23/p)=(29/p)=1 should be a more intelligent way to search for the smallest odd prime having -1 and the primes up to 29 as quadratic residues than using a complete sieve as described earlier. I am labeling this sequence as "hard" because extending it should become hard (exponentially hard, since each term should take roughly twice as much computation as the previous one) once the terms get to something around 20 digits.

I have now written a computer program to help me find members of this sequence. Among these, the term 3818929 is interesting because it is the first break in a pattern established by the previous terms, wherein the smallest prime p such that -1 and the primes up to the k-th prime are quadratic residues modulo p has the (k+1)st prime as a quadratic nonresidue. 3818929 is the smallest p to have -1 and the primes <= 41 as quadratic residues but it also has 43 (but not 47) as a quadratic residue. - David L. Harden, May 21 2005

This is A002224 with duplicates removed and 3 and 5 tacked on to the beginning. The remark about term 3818929 follows from the fact that it is the first duplicate in A002224.