A048868 - OEIS

%I #21 Dec 26 2024 23:17:00

%S 8,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,

%T 56,60,62,64,66,68,70,72,74,76,78,80,84,88,90,96,98,100,102,104,108,

%U 110,112,114,120,126,130,132,138,140,144,150,154,156,160,162,168,170

%N Numbers whose reduced residue system contains more primes than nonprimes.

%C From _Michael De Vlieger_, May 21 2017: (Start)

%C Conjecture: all terms are even.

%C 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), ...}.

%C 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)

%H Michael De Vlieger, <a href="/A048868/b048868.txt">Table of n, a(n) for n = 1..586</a> (a(n) < 10^5, no more terms < 10^8 checked by David A. Corneth).

%H Michael De Vlieger, <a href="/A048868/a048868.txt">Values of a(n), their differences, and multiplicity notation of their differences</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Reduced_residue_system">Reduced residue system</a>.

%e 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.

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

%o (PARI)

%o is(n) = {my(f = factor(n), e = eulerphi(f), o = omega(f), pr = primepi(n) - o, c = e - pr); c < pr

%o } \\ _David A. Corneth_, Jun 09 2024

%o (PARI)

%o upto(n) = {

%o 	my(res = List(), qp = 0, t = 0);

%o 	forfactored(i = 1, n,

%o 		if(isprime(i[1]),

%o 			qp++;

%o 		);

%o 		e = eulerphi(i[2]);

%o 		o = omega(i[2]);

%o 		if(e < (qp - o)<<1,

%o 			t++;

%o 			listput(res, i[1]);

%o 		);

%o 	);	

%o 	res

%o } \\ _David A. Corneth_, Jun 09 2024

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

%K nonn

%O 1,1

%A _Labos Elemer_