A386376 - OEIS

%I #29 Aug 26 2025 15:53:44

%S 1,1,1,2,1,1,1,2,5,1,1,4,1,1,1,4,1,3,1,2,1,1,1,2,2,1,2,2,1,1,1,2,1,1,

%T 1,2,1,1,1,8,1,1,1,2,7,1,1,8,3,7,1,2,1,7,1,2,1,1,1,6,1,1,5,2,1,1,1,2,

%U 1,1,1,2,1,1,6,2,1,1,1,6,5,1,1,4,1,1,1

%N a(n) is the smallest integer k such that b(n,k) is squarefree, where b(n,1) = n and b(n, k+1) = b(n,k) + rad(b(n, k)) for k >= 1.

%C rad(k) = A007947(k) is the largest squarefree integer dividing n.

%C Proof of a(n)'s existence: (Start)

%C Let c(n,k) = b(n,k) / rad(b(n,k)). Suppose that c(n,k) > 1 for all positive integers k. Pick k such that c(n,k) = m is the smallest. Let p be the smallest prime not dividing b(n,k). There exists an integer 1 <= i' <= p-1 such that p divides m + i'. So there exists a smallest integer 1 <= i <= i' such that m + i has a prime divisor not dividing b(n,k). From the minimality of i, for 1 <= j <= i-1, c(n,k+j) = m + j does not produce prime divisors not dividing b(n,k).

%C From the choice of i, there exists a prime q >= p such that q does not divide b(n,k) but q divides m + i. Then c(n,k+i) = (rad(b(n,k+i-1) * (c(n,k+i-1) + 1)) / rad(rad(b(n,k+i-1) * (c(n,k+i-1) + 1)) <= (c(n,k+i-1) + 1) / q <= (m + i) / p <= (m + p - 1) / p < m, because m > 1, a contradiction from the minimality of m. (End)

%e For n = 9, b(9,1) = 9, b(9,2) = 9 + rad(9) = 12, b(9,3) = 12 + rad(12) = 18, b(9,4) = 18 + rad(18) = 24, b(9,5) = 24 + rad(24) = 30 is squarefree, so a(9) = 5.

%t rad[m_]:=Times@@(First@# & /@ FactorInteger@ m);a[n_]:=Module[{k=1,b=n},While[!SquareFreeQ[b],k++;b=b+rad[b]];k];Array[a,87] (* _James C. McMahon_, Aug 25 2025 *)

%o (PARI) A007947(n) = factorback(factorint(n)[, 1]);

%o a(n) = {my(cnt = 1, x = n); while(x != A007947(x), x += A007947(x); cnt++); cnt};

%Y Cf. A005117, A007947.

%K nonn,easy

%O 1,4

%A _Yifan Xie_, Aug 20 2025