login
Largest integer k < n such that any prime factor of k is also a prime factor of n.
13

%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