login
Records in A300858.
2

%I #6 Apr 03 2018 16:07:31

%S 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,

%T 79,81,93,95,109,111,113,119,120,127,129,133,153,155,163,172,173,177,

%U 185,189,211,213,223,245,247,253,271,277,279,283,289,301,303,309,336

%N Records in A300858.

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

%e 0 is the first term since A300858(1) = 0. A300858 is 0 or negative for n < 8.

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

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

%t 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]]

%o (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

%o r=-1; for(x=1, oo, if(a300858(x) > r, r=a300858(x); print1(r, ", "))) \\ _Felix Fröhlich_, Mar 30 2018

%Y Cf. A243822, A243823, A300858, A300860.

%K nonn

%O 1,3

%A _Michael De Vlieger_, Mar 28 2018