|
%I #52 Mar 14 2021 17:09:16
%S 1,1,2,1,4,1,4,3,8,1,9,1,8,9,8,1,16,1,16,9,16,1,18,5,16,9,16,1,27,1,
%T 16,27,32,25,32,1,32,27,32,1,36,1,32,27,32,1,36,7,40,27,32,1,48,25,49,
%U 27,32,1,54,1,32,49,32,25,64,1,64,27,64,1,64,1,64,45,64,49,72,1,64,27
%N Largest integer k < n such that any prime factor of k is also a prime factor of n.
%C The function a(n) complements Euler's phi-function: 1) a(n)+phi(n) = n if n is a power of a prime (actually, in A285710). 2) It seems also that a(n)+phi(n) >= n for "almost all numbers" (see A285709, A208815). 3) a(2n) = n+1 if and only if n is a Mersenne prime. 4) Lim a(n^k)/n^k =1 if n has at least two prime factors and k goes to infinity.
%C From _Michael De Vlieger_, Apr 26 2017: (Start)
%C In other words, largest integer k < n such that k | n^e with integer e >= 0.
%C Penultimate term of row n in A162306. (The last term of row n in A162306 is n.)
%C For prime p, a(p) = 1. More generally, for n with omega(n) = 1, that is, a prime power p^e with e > 0, a(p^e) = p^(e - 1).
%C For n with omega(n) > 1, a(n) does not divide n. If n = pq with q = p + 2, then p^2 < n though p^2 does not divide n, yet p^2 | n^e with e > 1. If n has more than 2 distinct prime divisors p, powers p^m of these divisors will appear in the range (1..n-1) such that p^m > n/lpf(n) (lpf(n) = A020639(n)). Since a(n) is the largest of these, a(n) is not a divisor of n.
%C If a(n) does not divide n, then a(n) appears last in row n of A272618.
%C (End)
%H David W. Wilson, <a href="/A079277/b079277.txt">Table of n, a(n) for n = 2..10000</a>
%H Aled Walker and Alexander Walker, <a href="https://arxiv.org/abs/1809.02430">Arithmetic Progressions with Restricted Digits</a>, arXiv:1809.02430 [math.NT], 2018.
%F Largest k < n with rad(kn) = rad(n), where rad = A007947.
%e a(10)=8 since 8 is the largest integer< 10 that can be written using only the primes 2 and 5. a(78)=72 since 72 is the largest number less than 78 that can be written using only the primes 2, 3 and 13. (78=2*3*13).
%t Table[If[n == 2, 1, Module[{k = n - 2, e = Floor@ Log2@ n}, While[PowerMod[n, e, k] != 0, k--]; k]], {n, 2, 81}] (* _Michael De Vlieger_, Apr 26 2017 *)
%o (PARI) a(n) = {forstep(k = n - 1, 2, -1, f = factor(k); okk = 1; for (i=1, #f~, if ((n % f[i,1]) != 0, okk = 0; break;)); if (okk, return (k));); return (1);} \\ _Michel Marcus_, Jun 11 2013
%o (PARI)
%o A007947(n) = factorback(factorint(n)[, 1]); \\ _Andrew Lelechenko_, May 09 2014
%o A079277(n) = { my(r); if((n > 1 && !bitand(n,(n-1))), (n/2), r=A007947(n); if(1==n,0,k = n-1; while(A007947(k*n) <> r, k = k-1); k)); }; \\ _Antti Karttunen_, Apr 26 2017
%o (Python)
%o from sympy import divisors
%o from sympy.ntheory.factor_ import core
%o def a007947(n): return max(d for d in divisors(n) if core(d) == d)
%o def a(n):
%o k=n - 1
%o while True:
%o if a007947(k*n) == a007947(n): return k
%o else: k-=1
%o print([a(n) for n in range(2, 101)]) # _Indranil Ghosh_, Apr 26 2017
%Y Cf. A000010, A007947, A051953, A162306, A208815, A272618, A285328, A285699, A285707, A285709, A285710, A285711.
%K nonn,look
%O 2,3
%A Istvan Beck (istbe(AT)online.no), Feb 07 2003
|
