A048868 Numbers whose reduced residue system contains more primes than nonprimes.

8, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 84, 88, 90, 96, 98, 100, 102, 104, 108, 110, 112, 114, 120, 126, 130, 132, 138, 140, 144, 150, 154, 156, 160, 162, 168, 170

Offset: 1

Author

Labos Elemer

Keywords

• nonn

Comments

From Michael De Vlieger, May 21 2017: (Start)

Conjecture: all terms are even.

Let b(n) = differences of a(n). Many of the terms in b(n) are in A060735(n), i.e., b(n) >= A002110(n) and divisible by A002110(n). The smallest b(n) that is not in A060735 is b(450) = 66; b(450) > A002110(n) but not divisible by it; instead it is divisible by A002110(n-1). b(n) seems to "prefer" values of A002110(n) as n increases. There is a run of 22 values of 2 starting at b(2), of 22 values of 6 starting at b(178), of 7 values of 210 starting at b(543), and 3 values of 2310 starting at b(577). In the case of A002110(n) with n < 3, the length of runs of A002110(n) is greater than that of runs of any other number of comparable magnitude. The last observed position of A002110(n) in b(n) is {201, 442, (557), ...}.

Questions: are there increasingly more terms such that b(n) is not in A060735 as n increases? Are terms such that b(n) is in A060735 prevalent? Why does b(n) seem to "prefer" values in A002110 at certain magnitudes of n as n increases? Are there differences of a(n) = A002110(k) at positions greater than those observed, and if not, why? (End)

Examples

			n=30 is the largest extremal example whose reduced residue system consists only of primes and 1 (see A048597); n=8 Phi(8)=4, reduced residue system (8)={1,3,5,7} n=32 Phi(32)=16, reduced residue system (32)={1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31} of which only {1,9,15,21,25,27} are not primes, 10 are primes: 10 > 6 thus 32 belongs here.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..586 (a(n) < 10^5, no more terms < 10^8 checked by David A. Corneth).
• Michael De Vlieger, Values of a(n), their differences, and multiplicity notation of their differences.
• Wikipedia, Reduced residue system.

Crossrefs

A000720(n) - A001221(n) > A000010(n) - (A000720(n)-A001221(n)).

Programs

Mathematica

Select[Range@ 170, Function[n, Count[Range@ n, ?(PrimeQ@ # && CoprimeQ[n, #] &)] > EulerPhi[n]/2]] (* _Michael De Vlieger, May 21 2017 *)

PARI

is(n) = {my(f = factor(n), e = eulerphi(f), o = omega(f), pr = primepi(n) - o, c = e - pr); c < pr
} \\ David A. Corneth, Jun 09 2024

PARI

upto(n) = {
	my(res = List(), qp = 0, t = 0);
	forfactored(i = 1, n,
		if(isprime(i[1]),
			qp++;
		);
		e = eulerphi(i[2]);
		o = omega(i[2]);
		if(e < (qp - o)<<1,
			t++;
			listput(res, i[1]);
		);
	);	
	res
} \\ David A. Corneth, Jun 09 2024