A121998 -id:A121998 - cp's OEIS frontend

A381801 Irregular triangle read by rows: row n lists the residues r mod n of numbers k such that rad(k) | n, where rad = A007947.

0, 0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 4, 0, 1, 0, 1, 2, 4, 0, 1, 3, 0, 1, 2, 4, 5, 6, 8, 0, 1, 0, 1, 2, 3, 4, 6, 8, 9, 0, 1, 0, 1, 2, 4, 7, 8, 0, 1, 3, 5, 6, 9, 10, 12, 0, 1, 2, 4, 8, 0, 1, 0, 1, 2, 3, 4, 6, 8, 9, 10, 12, 14, 16, 0, 1, 0, 1, 2, 4, 5, 8, 10, 12, 16

Offset: 1

Michael De Vlieger, Mar 07 2025

Define S(p,n) to be the set of residues r (mod n) taken by the power range of prime divisor p, i.e., {p^m, m >= 1}.
Define T(n) to be the union of the tensor product of distinct terms in S(p,n) for all p|n, where the products are expressed mod n.
Row n of this triangle is T(n), a superset of row n of A381799.
For n > 1, the intersection of row n of this triangle and row n of A038566 is {1}.

			Table of c(n) = A381800(n) and T(n) for select n:
 n  c(n)  T(n)
-----------------------------------------------------------------------------
 1    1   {0}
 2    2   {0, 1}
 3    2   {0, 1}
 4    3   {0, 1, 2}
 5    2   {0, 1}
 6    5   {0, 1, 2, 3, 4}
 8    4   {0, 1, 2, 4}
 9    3   {0, 1, 3}
10    7   {0, 1, 2, 4, 5, 6, 8}
11    2   {0, 1}
12    8   {0, 1, 2, 3, 4, 6, 8, 9}
14    6   {0, 1, 2, 4, 7, 8}
15    8   {0, 1, 3, 5, 6, 9, 10, 12}
16    5   {0, 1, 2, 4, 8}
18   12   {0, 1, 2, 3, 4, 6, 8, 9, 10, 12, 14, 16}
20    9   {0, 1, 2, 4, 5, 8, 10, 12, 16}
24   11   {0, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18}
28    9   {0, 1, 2, 4, 7, 8, 14, 16, 21}
30   19   {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 21, 24, 25, 27}
36   16   {0, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 20, 24, 27, 28, 32}
For n = 10, we have S(2,10) = {1, 2, 4, 6, 8} and S(5,10) = {1, 5}. Therefore we have the following distinct products:
   1  2  4  8  6
   5  0
Hence T(10) = {0, 1, 2, 4, 5, 6, 8}; terms in A003592 belong to these residues (mod 10).
For n = 12, we have S(2,12) = {1, 2, 4, 8} and S(3,12) = {1, 3, 9}. Therefore we have the following distinct products:
   1  2  4  8
   3  6  0
   9
Thus T(12) = {0, 1, 2, 3, 4, 6, 8, 9}, terms in A003586 belong to these residues (mod 12).
For n = 30, we have {1, 2, 4, 8, 16}, {1, 3, 9, 21, 27}, and {1, 5, 25}. Therefore we have the following distinct products:
   1  2  4  8  16         5  10  20         25
   3  6 12 24            15   0
   9 18
  27
Thus T(30) = {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 21, 24, 25, 27}; terms in A051037 belong to these residues (mod 30).

Michael De Vlieger, Table of n, a(n) for n = 1..22906 (rows n = 1..500, flattened)
Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..36, showing reduced residues mod n in gray and labeling terms in row n. The number n appears on the left in red italic, and row length A381800(n) in blue at right.
Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..5000.

Cf. A007947, A038566, A121998, A162306, A381799, A381800.

Table[Union@ Flatten@ Mod[TensorProduct @@ Map[(p = #; NestWhileList[Mod[p*#, n] &, 1, UnsameQ, All]) &, FactorInteger[n][[All, 1]] ], n], {n, 30}]

Row 1 is {0} since 1 is the empty product and the only number that has zero prime factors is 1, congruent to 0 (mod 1).
Row n begins with {0,1} for n > 1.
For prime p, row p = {0,1}.
For prime power p^m, m > 0, row p = union of {0} and {p^i, i < m}.
Row n is a subset of row n of A121998, considering n in A121998 instead as n mod n = 0.
Row n is a superset of row n of A162306, considering n in A162306 instead as n mod n = 0.

A381799 Irregular triangle read by rows, where row n is a list of residues of powers of prime factors of n (mod n).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 2, 0, 1, 1, 2, 3, 4, 0, 1, 0, 1, 2, 4, 0, 1, 3, 1, 2, 4, 5, 6, 8, 0, 1, 1, 2, 3, 4, 8, 9, 0, 1, 1, 2, 4, 7, 8, 1, 3, 5, 6, 9, 10, 12, 0, 1, 2, 4, 8, 0, 1, 1, 2, 3, 4, 8, 9, 10, 14, 16, 0, 1, 1, 2, 4, 5, 8, 12, 16, 1, 3, 6, 7, 9, 12, 15, 18

Offset: 1

Michael De Vlieger, Mar 07 2025

Define S(p,n) to be the set of residues r (mod n) taken by the power range of prime divisor p, i.e., {p^m, m >= 1}. Examples: S(2,10) = {1, 2, 4, 8, 6}, while S(2,8) = {0, 1, 2, 4} and S(2,12) = {1, 2, 4, 8}; S(3,6) = {1, 3}, S(3,9) = {0, 1, 3}, S(3,12) = {1, 3, 9}, etc.
Define T(n) to be the (sorted) union of S(p,n) for all prime factors p | n.
Row n of this table is T(n).
For n > 1, the intersection of row n of this table and row n of A038566 is {1}. Thus, 1 appears in each row except for n = 1, since p^0 = 1 for all primes p | n.
The number 0 appears in T(p^m) (where p is prime and m >= 1) since p^m is congruent to 0 (mod p^m).
Zero does not appear in T(n) for n in A024619.

			Triangle begins:
 n   row n
--------------------------
 1:  0;
 2:  0, 1;
 3:  0, 1;
 4:  0, 1, 2;
 5:  0, 1;
 6:  1, 2, 3, 4;
 7:  0, 1;
 8:  0, 1, 2, 4;
 9:  0, 1, 3;
10:  1, 2, 4, 5, 6, 8;
11:  0, 1;
12:  1, 2, 3, 4, 8, 9; etc.
For n = 10, we have S(2,10) = {1, 2, 4, 8, 6}, S(5,10) = {1, 5}, thus T(10) = {1, 2, 4, 5, 6, 8}.
For n = 12, we have S(2,12) = {1, 2, 4, 8}, S(3,12) = {1, 3, 9}, thus T(12) = {1, 2, 3, 4, 8, 9}.
For n = 16, we have S(2,16) = {1, 2, 4, 8, 0}, thus T(16) = {0, 1, 2, 4, 8}.
For n = 30, we have S(2,30) = {1, 2, 4, 8, 16}, S(3,30) = {1, 3, 9, 27, 21}, and S(5,30) = {1, 5, 25}, so T(30) = {1, 2, 3, 4, 5, 8, 9, 16, 21, 25, 27}, etc.

Michael De Vlieger, Table of n, a(n) for n = 1..17305 (rows n = 1..500, flattened.)
Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..36, showing reduced residues mod n in gray and labeling terms in row n. The number n appears on the left in red italic, and row length A381798(n) in blue at right.
Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..5000.

Cf. A024619, A038566, A121998, A381798.

{{0}}~Join~Table[Union@ Flatten@ Map[(p = #; NestWhileList[Mod[p*#, n] &, 1, UnsameQ, All]) &, FactorInteger[n][[All, 1]] ], {n, 2, 30}]

Row 1 = {0} since 1 is the empty product.
For prime p, row p is {0, 1}.
For proper prime power p^m, m > 1, row p^m is the union of {0} and p^i, i < m.
A381798(n) = length of row n.

A331888 Number of compositions (ordered partitions) of n into parts having a common factor > 1 with n.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 5, 1, 8, 4, 17, 1, 60, 1, 65, 19, 128, 1, 800, 1, 683, 67, 1025, 1, 11005, 16, 4097, 256, 9203, 1, 369426, 1, 32768, 1027, 65537, 79, 2124475, 1, 262145, 4099, 1424118, 1, 48987720, 1, 2127107, 96334, 4194305, 1, 411836297, 64, 67919981, 65539

Offset: 0

Ilya Gutkovskiy, Jan 30 2020

nonn

			a(9) = 4 because we have [9], [6, 3], [3, 6] and [3, 3, 3].

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for sequences related to compositions

Cf. A182986 (positions of 1's), A100347, A121998, A178472, A331885, A331887.

a:= proc(m) option remember; local b; b:=
      proc(n) option remember; `if`(n=0, 1,
        add(`if`(igcd(j, m)>1, b(n-j), 0), j=1..n))
      end; forget(b); b(m$2)
    end:
seq(a(n), n=0..82);  # Alois P. Heinz, Jan 30 2020

Table[SeriesCoefficient[1/(1 - Sum[Boole[GCD[k, n] > 1] x^k, {k, 1, n}]), {x, 0, n}], {n, 0, 51}]

a(n) = [x^n] 1 / (1 - Sum_{k: gcd(n,k) > 1} x^k).

A381094 Triangle read by rows where row n contains k < n that are neither coprime to n nor have the same squarefree kernel as n, or 0 if there are no such k.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 3, 4, 0, 6, 6, 2, 4, 5, 6, 8, 0, 2, 3, 4, 8, 9, 10, 0, 2, 4, 6, 7, 8, 10, 12, 3, 5, 6, 9, 10, 12, 6, 10, 12, 14, 0, 2, 3, 4, 8, 9, 10, 14, 15, 16, 0, 2, 4, 5, 6, 8, 12, 14, 15, 16, 18, 3, 6, 7, 9, 12, 14, 15, 18, 2, 4, 6, 8, 10, 11, 12, 14, 16, 18, 20

Offset: 1

Michael De Vlieger, Feb 14 2025

Let rad(k) = A007947(k), the squarefree kernel of k.
Let T(n) be row n of this sequence and let S(n) be row n of A133995.
T(n) contains numbers k < n such that k and n share at least one prime factor p, but not all distinct prime p | n.
T(n) is a superset of S(n), since S(n) does not contain any divisor d | n, while T(n) allows d | n such that rad(d) != rad(n).

			Table begins:
   n   row n
  ---------------------------
   1:  0;
   2:  0;
   3:  0;
   4:  0;
   5:  0;
   6:  2, 3, 4;
   7:  0;
   8:  6;
   9:  6;
  10:  2, 4, 5, 6, 8;
  11:  0;
  12:  2, 3, 4, 8, 9, 10;
  13:  0;
  14:  2, 4, 6, 7, 8, 10, 12;
  15:  3, 5, 6, 9, 10, 12;
  16:  6, 10, 12, 14;
From _Michael De Vlieger_, Mar 03 2025: (Start)
Row 10 is the union of {2, 4, 6, 8, 10} and {5, 10} without 10.
Row 12 is the union of {2, 4, 6, 8, 10, 12} and {3, 6, 9, 12} without {6, 12}.
Row 30 is the union of {2, 4, ..., 30}, {3, 6, ..., 30}, and {5, 10, ..., 30} without 30.
Row 84 is the union of {2, 4, ..., 84}, {3, 6, ..., 84}, and {7, 14, ..., 84} without {42, 84}, etc. (End)

Michael De Vlieger, Table of n, a(n) for n = 1..11873 (rows n = 1..250, flattened)

Cf. A007947, A121998, A133995, A369609, A381096.

rad[x_] := rad[x] = Times @@ FactorInteger[x][[All, 1]]; Table[r = rad[n]; Select[Range[n], Nor[CoprimeQ[#, n], rad[#] == r] &], {n, 120}]

T(n) = { k < n : 1 < gcd(k,n), rad(k) != rad(n) }.
T(n) = S(n) \ { k : k | n, rad(k) = rad(n) }.
For prime p, T(p) = {}, but we write 0 to signify the empty set.
T(4) = 0, since k < 4 is either coprime to 4 or rad(k) = 2.
Let U(n) be row n of A121998 and let R(n) be row n of A369609. T(n) = U(n) \ R(n). - Michael De Vlieger, Mar 03 2025

A300858 a(n) = A243823(n) - A243822(n).

Original entry on oeis.org

0, 0, 0, 0, 0, -1, 0, 1, 1, -1, 0, -1, 0, 1, 2, 4, 0, -1, 0, 3, 4, 3, 0, 3, 3, 5, 6, 7, 0, -5, 0, 11, 6, 7, 6, 6, 0, 9, 8, 11, 0, 1, 0, 13, 12, 13, 0, 13, 5, 13, 12, 17, 0, 13, 10, 19, 14, 19, 0, 5, 0, 21, 18, 26, 12, 11, 0, 23, 18, 15, 0, 25, 0, 25, 24, 27

Offset: 1

Michael De Vlieger, Mar 14 2018

sign

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 is the difference between the latter and the former species of nondivisors in the cototient of n.
Since A045763(n) = A243822(n) + A243823(n), this sequence examines the balance of the two components among nondivisors in the cototient of n.
For positive n < 6 and for p prime, a(n) = a(p) = 0, thus a(A046022(n)) = 0.
For prime powers p^e, a(p^e) = A243823(p^e), since A243822(p^e) = 0, thus a(n) = A243823(n) for n in A000961.
Value of a(n) is generally nonnegative; a(n) is negative for n = {6, 10, 12, 18, 30}; a(30) = -5, but a(n) = -1 for the rest of the aforementioned numbers. These five numbers are a subset of A295523.

			a(6) = -1 since the only nondivisor in the cototient of 6 is 4, which divides 6^e with e > 1; therefore 0 - 1 = -1.
a(8) = 1 since the only nondivisor in the cototient of 8 is 6, and 6 does not divide 8^e with e > 1, therefore 1 - 0 = 1.
Some values of a(n) and related sequences:
   n  a(n) A243823(n) A243822(n)    A272619(n)       A272618(n)
  -------------------------------------------------------------
   1   0          0          0      -                -
   2   0          0          0      -                -
   3   0          0          0      -                -
   4   0          0          0      -                -
   5   0          0          0      -                -
   6  -1          0          1      -                {4}
   7   0          0          0      -                -
   8   1          1          0      {6}              -
   9   1          1          0      {6}              -
  10  -1          1          2      {6}              {4,8}
  11   0          0          0      -                -
  12  -1          1          2      {10}             {8,9}
  13   0          0          0      -                -
  14   1          3          2      {6,10,12}        {4,8}
  15   2          3          1      {6,10,12}        {9}
  16   4          4          0      {6,10,12,14}     -
  17   0          0          0      -                -
  18  -1          3          4      {10,14,15}       {4,8,12,16}
  19   0          0          0      -                -
  20   3          5          2      {6,12,14,15,18}  {8,16}
  ...

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000005, A000010, A000961, A010846, A046022, A121998, A133995, A173540, A243822, A243823, A272618, A272619, A295523, A300859, A300861.

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

a(n) = 1 + n + numdiv(n) - eulerphi(n) - 2*sum(k=1, n, if(gcd(n,k)-1, 0, moebius(k)*(n\k))); \\ Michel Marcus, Mar 17 2018

a(n) = 1 + n - A000010(n) - 2*A010846(n) + A000005(n).

A331885 Number of partitions of n into parts having a common factor > 1 with n.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 16, 9, 22, 1, 51, 1, 51, 17, 57, 1, 147, 7, 102, 30, 152, 1, 620, 1, 231, 58, 298, 21, 946, 1, 491, 103, 921, 1, 3249, 1, 1060, 325, 1256, 1, 4866, 15, 3157, 299, 2539, 1, 10369, 62, 4846, 492, 4566, 1, 45786, 1, 6843

Offset: 0

Ilya Gutkovskiy, Jan 30 2020

nonn

			a(6) = 4 because we have [6], [4, 2], [3, 3] and [2, 2, 2].

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for sequences related to partitions

Cf. A182986 (positions of 1's), A018783, A057562, A121998, A331887, A331888.

a:= proc(m) option remember; local b; b:=
      proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
       `if`(igcd(i, m)>1, b(n-i, min(i, n-i)), 0)+b(n, i-1)))
      end; forget(b); b(m$2)
    end:
seq(a(n), n=0..82);  # Alois P. Heinz, Jan 30 2020

Table[SeriesCoefficient[Product[1/(1 - Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 62}]

a(n) = [x^n] Product_{k: gcd(n,k) > 1} 1 / (1 - x^k).

A331887 Number of partitions of n into distinct parts having a common factor > 1 with n.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 3, 1, 5, 1, 5, 4, 6, 1, 11, 1, 11, 6, 12, 1, 23, 3, 18, 8, 23, 1, 69, 1, 32, 13, 38, 7, 84, 1, 54, 19, 79, 1, 224, 1, 90, 46, 104, 1, 264, 5, 187, 39, 166, 1, 449, 14, 251, 55, 256, 1, 1374, 1, 340, 111, 390, 20, 1692, 1, 513, 105, 1610

Offset: 0

Ilya Gutkovskiy, Jan 30 2020

nonn

			a(12) = 5 because we have [12], [10, 2], [9, 3], [8, 4] and [6, 4, 2].

Antti Karttunen, Table of n, a(n) for n = 0..10416
Index entries for sequences related to partitions

Cf. A036998, A121998, A175787 (positions of 1's), A303280, A331885, A331888.

a:= proc(m) option remember; local b; b:=
      proc(n, i) option remember; `if`(i*(i+1)/21, b(n-i, min(i-1, n-i)), 0)+b(n, i-1)))
      end; forget(b); b(m$2)
    end:
seq(a(n), n=0..82);  # Alois P. Heinz, Jan 30 2020

Table[SeriesCoefficient[Product[(1 + Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 70}]

A331887(n) = { my(p = Ser(1, 'x, 1+n)); for(k=2, n, if(gcd(n,k)>1, p *= (1 + 'x^k))); polcoef(p, n); }; \\ Antti Karttunen, Jan 25 2025

a(n) = [x^n] Product_{k: gcd(n,k) > 1} (1 + x^k).

A381497 a(n) = sum of numbers k < n such that 1 < gcd(k,n) and rad(k) != rad(n), where rad = A007947.

Original entry on oeis.org

0, 0, 0, 0, 0, 9, 0, 6, 6, 25, 0, 36, 0, 49, 45, 42, 0, 81, 0, 100, 84, 121, 0, 144, 45, 169, 96, 196, 0, 315, 0, 210, 198, 289, 175, 354, 0, 361, 273, 430, 0, 609, 0, 484, 435, 529, 0, 648, 140, 655, 459, 676, 0, 801, 385, 826, 570, 841, 0, 1260, 0, 961, 798

Offset: 1

Michael De Vlieger, Mar 02 2025

nonn

Analogous to A066760(n), the sum of row n of A133995, and A381499(n), sum of row n of A272619.

			Table of n and a(n) for select n, showing prime power decomposition of both and row n of A381094:
   n   Factor(n) a(n)  Factor(a(n))  Row n of A381094
  -------------------------------------------------------------------
   6   2 * 3       9   3^2           {2,3,4}
   8   2^3         6   2 * 3         {6}
   9   3^2         6   2 * 3         {6}
  10   2 * 5      25   5^2           {2,4,5,6,8}
  12   2^2 * 3    36   2^2 * 3^2     {2,3,4,8,9,10}
  14   2 * 7      49   7^2           {2,4,6,7,8,10,12}
  15   3 * 5      45   3^2 * 5       {3,5,6,9,10,12}
  16   2^4        42   2 * 3 * 7     {6,10,12,14}
  18   2 * 3^2    81   3^4           {2,3,4,8,9,10,14,15,16}
  20   2^2 * 5   100   2^2 * 5^2     {2,4,5,6,8,12,14,15,16,18}
  21   3 * 7      84   2^2 * 3 * 7   {3,6,7,9,12,14,15,18}
  22   2 * 11    121   11^2          {2,4,6,8,10,11,12,14,16,18,20}
  24   2^3 * 3   144   2^4 * 3^2     {2,3,4,8,9,10,14,15,16,20,21,22}
a(6) = (2+4) + (3) = 9,
a(n) = 6 for n in {8, 9} since 6 is the only number less than n that shares a factor with n but does not have the same squarefree kernel as n.
a(10) = (2+4+6+8) + (5) = 25.
a(12) = (2+4+8+10) + (3+9) = 36.
a(14) = (2+4+6+8+10+12) + (7) = 49.
a(15) = (3+6+9+12) + (5+10) = 45.
a(16) = (6+10+12+14) = 42, etc.

Michael De Vlieger, Table of n, a(n) for n = 1..16384
Michael De Vlieger, Log log scatterplot of a(n), n = 6..2^14, ignoring a(n) = 0, showing a(n) for prime power n in gold, a(n) for squarefree n in green, otherwise blue.

Cf. A007947, A038566, A066760, A067392, A121998, A369609, A381094, A381096, A381498, A381499.

rad[x_] := rad[x] = Times @@ FactorInteger[x][[All, 1]]; Table[r = rad[n]; Total@ Select[Range[n], Nor[CoprimeQ[#, n], rad[#] == r] &], {n, 120}]

a(n) is the sum of row n of A381094.
a(n) = 0 for prime n and n = 4.
a(n) = A067392(n) - A381498(n).

A300860 Indices of records in A300858.

Original entry on oeis.org

1, 8, 15, 16, 26, 27, 28, 32, 44, 52, 56, 62, 64, 76, 80, 88, 96, 100, 104, 112, 122, 124, 128, 144, 160, 176, 184, 192, 200, 216, 246, 248, 250, 256, 272, 276, 282, 288, 318, 320, 324, 348, 354, 366, 372, 384, 414, 426, 432, 468, 474, 486, 516, 522, 528, 534

Offset: 1

Michael De Vlieger, Mar 14 2018

nonn

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 record setters in the sequence A300858(n), which is a function that represents the difference between the latter and the former species of nondivisors in the cototient of n.
Odd terms m < 36,000,000: {1, 15, 27}.
Smallest term m with A001221(m) = {0, 1, 2, ..., 8} = {1, 8, 15, 246, 2010, 9870, 30030, 510510, 9699690} (the last 3 terms are in A002110).
Smallest term m with A001222(m) = {0, 2, 3, ..., 12} = {1, 15, 8, 16, 32, 64, 128, 256, 768, 1536, 7680, 53760, 3843840} (includes 2^e with 3 <= e <= 8). Note, A300858(p) for p prime = 0.

			8 is in the sequence because A300858(n) for n < 8 is negative or 0 after A300858(1) = 0. 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.)
15 is in the sequence because -1 <= A300858(n) <= 1 for n < 15. 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.

Michael De Vlieger, Table of n, a(n) for n = 1..1710
Michael De Vlieger, Decomposition of terms in A300860 and Related Sequences.

Cf. A001221, A001222, A243822, A243823, A300858.

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

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
r=-1; for(i=1, oo, if(a300858(i) > r, print1(i, ", "); r=a300858(i))) \\ Felix Fröhlich, Mar 30 2018

A300861 Records in A300858.

Original entry on oeis.org

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

Michael De Vlieger, Mar 28 2018

nonn

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.

			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.

Cf. A243822, A243823, A300858, A300860.

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

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

cp's OEIS Frontend

A381801 Irregular triangle read by rows: row n lists the residues r mod n of numbers k such that rad(k) | n, where rad = A007947.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A381799 Irregular triangle read by rows, where row n is a list of residues of powers of prime factors of n (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A331888 Number of compositions (ordered partitions) of n into parts having a common factor > 1 with n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A381094 Triangle read by rows where row n contains k < n that are neither coprime to n nor have the same squarefree kernel as n, or 0 if there are no such k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A300858 a(n) = A243823(n) - A243822(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A331885 Number of partitions of n into parts having a common factor > 1 with n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A331887 Number of partitions of n into distinct parts having a common factor > 1 with n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula