login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A079277 Largest integer k < n such that any prime factor of k is also a prime factor of n. 10
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

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.

From Michael De Vlieger, Apr 26 2017: (Start)

In other words, largest integer k < n such that k | n^e with integer e >= 0.

Penultimate term of row n in A162306. (The last term of row n in A162306 is n.)

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).

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.

If a(n) does not divide n, then a(n) appears last in row n of A272618.

(End)

LINKS

David W. Wilson, Table of n, a(n) for n = 2..10000

FORMULA

Largest k < n with rad(kn) = rad(n), where rad = A007947.

EXAMPLE

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).

MATHEMATICA

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 *)

PROG

(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

(PARI)

A007947(n) = factorback(factorint(n)[, 1]); \\ From Andrew Lelechenko, May 09 2014

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

(Python)

from sympy import divisors

from sympy.ntheory.factor_ import core

def a007947(n): return max(list(filter(lambda i: core(i) == i, divisors(n))))

def a(n):

    k=n - 1

    while True:

        if a007947(k*n) == a007947(n): return k

        else: k-=1

print [a(n) for n in xrange(2, 101)] # Indranil Ghosh, Apr 26 2017

CROSSREFS

Cf. A000010, A007947, A051953, A162306, A208815, A272618, A285328, A285699, A285707, A285709, A285710, A285711.

Sequence in context: A024994 A243329 A051953 * A066452 A007104 A102627

Adjacent sequences:  A079274 A079275 A079276 * A079278 A079279 A079280

KEYWORD

nonn

AUTHOR

Istvan Beck (istbe(AT)online.no), Feb 07 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 27 07:55 EDT 2017. Contains 287202 sequences.