A363061 Number of k <= P(n) such that rad(k) | P(n), where rad(n) = A007947(n) and P(n) = A002110(n).

1, 2, 5, 18, 68, 283, 1161, 4843, 19985, 83074, 349670, 1456458, 6107257, 25547835, 106115655, 440396113, 1833079809, 7642924612, 31705433101, 131711607956, 546283729493, 2257462298234, 9339325821411, 38593708318690, 159600066415313, 661371515924516, 2736805917843710

Offset: 0

Author

Michael De Vlieger, Jun 16 2023

Keywords

• nonn
• hard

Examples

			a(0) = 1 since P(0) = 1 and 1 | 1.
a(1) = 2 since P(1) = 2 and both 1 | 2 and 2 | 2.
a(2) = 5 since P(2) = 6 and rad(m) | 6 for m = {1, 2, 3, 4, 6}.
a(3) = 18 since P(3) = 30 and rad(m) | 30 for m = {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30}, etc.
Regarding a(3), we see that there are 18 terms in the tensor product of prime power ranges of 2, 3, and 5 that do not exceed 30:
5^0X | 2^0 2^1 2^2 2^3 2^4    5^1X | 2^0 2^1 2^2    5^2X | 2^0
--------------------------    ------------------    ----------
3^0  |   1   2   4   8  16    3^0  |   5  10  20    3^0  |  25
3^1  |   3   6  12  24        3^1  |  15  30
3^2  |   9  18
3^3  |  27
Hence, a(3) = 18. This approach proves handy for larger n.
		

Links

• Bert Dobbelaere, Python program

Crossrefs

Cf. A002110, A007947, A010846.

Programs

Mathematica

f[1] = 1; f[n_] := Function[w,
ToExpression@ StringJoin["Block[{n = ", ToString@ n,
    ", k = 0}, Flatten@ Table[k++, ",
    Most@ Flatten@ Map[{#, ", "} &, #], "]; k]"] &@
      MapIndexed[
        Function[p, StringJoin["{", ToString@ Last@ p, ", 0, Log[",
          ToString@ First@ p, ", n/(",
          ToString@ InputForm[Times @@ Map[Power @@ # &, Take[w, First@ #2 - 1]]],
          ")]}"] ]@ w[[First@ #2]] &, w]]@
   Map[{#, ToExpression["p" <> ToString@ PrimePi@ #]} &,
     FactorInteger[n][[All, 1]]];
   Map[f, FoldList[Times, 1, Prime@ Range@ 9] ]

Formula

a(n) = A010846(A002110(n)).

a(n) >= 2^n.

Extensions

Corrected a(15) and added a(16)-a(23) from Bert Dobbelaere, Jun 27 2023

a(24)-a(26) from Martin Ehrenstein, Jul 08 2023