A300861 Records in A300858.

0, 1, 2, 4, 5, 6, 7, 11, 13, 17, 19, 21, 26, 27, 31, 35, 37, 40, 43, 47, 49, 51, 57, 66, 73, 79, 81, 93, 95, 109, 111, 113, 119, 120, 127, 129, 133, 153, 155, 163, 172, 173, 177, 185, 189, 211, 213, 223, 245, 247, 253, 271, 277, 279, 283, 289, 301, 303, 309, 336

Offset: 1

Author

Michael De Vlieger, Mar 28 2018

Keywords

• nonn

Comments

Consider numbers in the cototient of n, listed in row n of A121998. For composite n > 4, there are nondivisors m in the cototient, listed in row n of A133995. Of these m, there are two species. The first are m that divide n^e with integer e > 1, while the last do not divide n^e. These are listed in row n of A272618 and A272619, and counted by A243822(n) and A243823(n), respectively. This sequence lists the records in A300858, which is a function that represents the difference between the latter and the former species of nondivisors in the cototient of n.

Examples

			0 is the first term since A300858(1) = 0. A300858 is 0 or negative for n < 8.
A300858(8) = A243823(8) - A243822(8) = 1 - 0 = 1. Within the cototient of 8 there is one nondivisor (6) and it does not divide 8^e for integer e. (All prime powers m have A243822(m) = 0 and for m > 4, A243823(m) is positive.) Therefore 1 is the next term. Between 8 and 15, -1 <= A300858(n) <= 1.
A300858(15) = 2. Within the cototient of 15 there are 4 nondivisors; of these 3 (i.e., {6, 10, 12}) do not divide 15^e for integer e, but 9 | 15^2. Therefore 3 - 1 = 2 and 2 exceeds all values A300858(n) for n < 15, and appears after 1.
		

Crossrefs

Cf. A243822, A243823, A300858, A300860.

Programs

Mathematica

f[n_] := Count[Range@ n, _?(PowerMod[n, Floor@ Log2@ n, #] == 0 &)]; Union@ FoldList[Max, Array[#1 - #3 + 1 - 2 #2 + #4 & @@ {#, f@ #, EulerPhi@ #, DivisorSigma[0, #]} &, 600]]

PARI

a300858(n) = 1 + n + numdiv(n) - eulerphi(n) - 2*sum(k=1, n, if(gcd(n, k)-1, 0, moebius(k)*(n\k))) \\ after Michel Marcus in A300858
r=-1; for(x=1, oo, if(a300858(x) > r, r=a300858(x); print1(r, ", "))) \\ Felix Fröhlich, Mar 30 2018