A175787 -id:A175787 - cp's OEIS frontend

A161344 Numbers k with A033676(k)=2, where A033676 is the largest divisor <= sqrt(k).

4, 6, 8, 10, 14, 22, 26, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 134, 142, 146, 158, 166, 178, 194, 202, 206, 214, 218, 226, 254, 262, 274, 278, 298, 302, 314, 326, 334, 346, 358, 362, 382, 386, 394, 398, 422, 446, 454, 458, 466, 478, 482, 502, 514

Offset: 1

Omar E. Pol, Jun 20 2009

Define a sieve operation with parameter s that eliminates integers of the form s^2 + s*i (i >= 0) from the set A000027 of natural numbers. The sequence lists those natural numbers that are eliminated by the sieve s=2 and cannot be eliminated by any sieve s >= 3. - R. J. Mathar, Jun 24 2009
After a(3)=8 all terms are 2*prime; for n > 3, a(n) = 2*prime(n-1) = 2*A000040(n-1). - Zak Seidov, Jul 18 2009
From Omar E. Pol, Jul 18 2009: (Start)
A classification of the natural numbers A000027.
=============================================================
Numbers k whose largest divisor <= sqrt(k) equals j
=============================================================
j       Sequence     Comment
=============================================================
1 ..... A008578      1 together with the prime numbers
2 ..... A161344      This sequence
3 ..... A161345
4 ..... A161424
5 ..... A161835
6 ..... A162526
7 ..... A162527
8 ..... A162528
9 ..... A162529
10 .... A162530
11 .... A162531
12 .... A162532
... And so on. (End)
The numbers k whose largest divisor <= sqrt(k) is j are exactly those numbers j*m where m is either a prime >= k or one of the numbers in row j of A163925. - Franklin T. Adams-Watters, Aug 06 2009
See also A163280, the main entry for this sequence. - Omar E. Pol, Oct 24 2009
Also A100484 UNION 8. - Omar E. Pol, Nov 29 2012 (after Seidov and Hasler)
Is this the union of {4} and A073582? - R. J. Mathar, May 30 2025

Omar E. Pol, Determinacion geometrica de los numeros primos y perfectos
Omar E. Pol, Illustration: Divisors and pi(x)
Omar E. Pol, Illustration of initial terms
Omar E. Pol. Illustration of initial terms of A008578, A161344, A161345, A161424

Cf. A000005, A018253, A160811, A160812, A161205, A161346, A033676, A008578, A161345, A161424, A161835, A162526, A162527, A162528, A162529, A162530, A162531, A162532, A163925.

Second column of array in A163280. Also, second row of array in A163990.

isA := proc(n,s) if n mod s <> 0 then RETURN(false); fi; if n/s-s >= 0 then RETURN(true); else RETURN(false); fi; end: isA161344 := proc(n) for s from 3 to n do if isA(n,s) then RETURN(false); fi; od: isA(n,2) ; end: for n from 1 to 3000 do if isA161344(n) then printf("%d,",n) ; fi; od; # R. J. Mathar, Jun 24 2009

a[n_] := If[n <= 3, 2n+2, 2*Prime[n-1]]; Table[a[n], {n, 1, 56}] (* Jean-François Alcover, Nov 26 2012, after Zak Seidov *)

a(n)=if(n>3,prime(n-1),n+1)*2 \\ M. F. Hasler, Nov 27 2012

Equals 2*A000040 union {8}. - M. F. Hasler, Nov 27 2012

a(n) = 2*A046022(n+1) = 2*A175787(n). - Omar E. Pol, Nov 27 2012

More terms from R. J. Mathar, Jun 24 2009

Definition added by R. J. Mathar, Jun 28 2009

A075254 a(n) = n + (sum of prime factors of n taken with repetition).

Original entry on oeis.org

1, 4, 6, 8, 10, 11, 14, 14, 15, 17, 22, 19, 26, 23, 23, 24, 34, 26, 38, 29, 31, 35, 46, 33, 35, 41, 36, 39, 58, 40, 62, 42, 47, 53, 47, 46, 74, 59, 55, 51, 82, 54, 86, 59, 56, 71, 94, 59, 63, 62, 71, 69, 106, 65, 71, 69, 79, 89, 118, 72, 122, 95, 76, 76, 83, 82, 134, 89, 95, 84, 142

Offset: 1

Zak Seidov, Sep 10 2002

a(n) = n + A001414(n).

Product of prime factors plus sum of prime factors of n. For minus instead of plus we have A075255, zeros A175787. - Gus Wiseman, Jan 26 2025

			a(6)=11 because 6=2*3, sopfr(6)=2+3=5 and 6+5=11.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

A000027 gives product of prime factors, indices A003963.
A000040 lists the primes, differences A001223.
A001414 gives sum of prime factors, indices A056239.
A027746 lists prime factors, indices A112798, count A001222.
A075255 gives product of prime factors minus sum of prime factors.
Cf. A000720, A001055, A001222, A008472, A090340, A096461 (iteration), A175508, A319000, A325036, A325037, A325038, A379681, A379682.

a075254 n = n + a001414 n  -- Reinhard Zumkeller, Feb 27 2012

[n eq 1 select 1 else (&+[p[1]*p[2]: p in Factorization(n)]) + n: n in [1..80]]; // G. C. Greubel, Jan 10 2019

A075254 := proc(n)
    n+A001414(n) ;
end proc: # R. J. Mathar, Jul 27 2015

Table[If[n==1,1, n +Plus@@Times@@@FactorInteger@n], {n, 80}] (* G. C. Greubel, Jan 10 2019 *)

a(n) = my(f = factor(n)); n + sum(k=1, #f~, f[k,1]*f[k,2]); \\ Michel Marcus, Feb 22 2017

[n + sum(factor(n)[j][0]*factor(n)[j][1] for j in range(0, len(factor(n)))) for n in range(1, 80)] # G. C. Greubel, Jan 10 2019

From Gus Wiseman, Jan 26 2025: (Start)
First differences are 1 - A090340(n).
a(n) = 2*n - A075255(n).
a(n) = 2*A001414(n) + A075255(n).
(End)

A011776 a(1) = 1; for n > 1, a(n) is defined by the property that n^a(n) divides n! but n^(a(n)+1) does not.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 5, 1, 2, 3, 3, 1, 4, 1, 4, 3, 2, 1, 7, 3, 2, 4, 4, 1, 7, 1, 6, 3, 2, 5, 8, 1, 2, 3, 9, 1, 6, 1, 4, 10, 2, 1, 11, 4, 6, 3, 4, 1, 8, 5, 9, 3, 2, 1, 14, 1, 2, 10, 10, 5, 6, 1, 4, 3, 11, 1, 17, 1, 2, 9, 4, 7, 6, 1, 19, 10, 2, 1, 13, 5, 2, 3, 8, 1, 21

Offset: 1

Robert G. Wilson v

From Stefano Spezia, Nov 08 2018: (Start)
It appears that for n > 1 a(n) = 1 iff n = 4 or a prime number (see A175787).
It appears that a(n) = 2 iff n is in A074845. (End)
Since a prime p is coprime to all positive integers less than p, a(p)=1. - Robert D. Rosales, Jun 17 2024
If n > 4 is composite then a(n) > 1. Proof: 1) If n is not a square of a prime, then n has a divisor d such that 1 < d < n/d < n, so d, n/d and n appear as different factors in n!, n^2 | n!, and therefore a(n) >= 2. 2) If n = p^2 is a square of a prime, then p, 2*p and p^2 appear as different factors in n! when p > 2, therefore a(n) >= 2 if n != 4. - Amiram Eldar, Jul 06 2024

			12^5 divides 12! but 12^6 does not so a(12) = 5.

Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., NY 1991.
Joe Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 251.

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Nick MacKinnon, How many times does n go into n!, The Mathematical Gazette, Vol. 70, No. 453 (1986), pp. 203-205.
Peter Shui, A footnote on the number of times n goes into n!, The Mathematical Gazette, Vol. 93, No. 528 (2009), pp. 492-495.
Eric Weisstein's World of Mathematics, Factorial.
Index entries for sequences related to factorial numbers.

Cf. A011777, A011778, A133481, A000142, A074845.
Diagonal of A090622.
Cf. A175787 (primes together with 4).

a011776 1 = 1
a011776 n = length $
   takeWhile ((== 0) . (mod (a000142 n))) $ iterate (* n) n
-- Reinhard Zumkeller, Sep 01 2012

a := []; for n from 2 to 200 do i := 0: while n! mod n^i = 0 do i := i+1: od: a := [op(a),i-1]; od: a;
# second Maple program:
f:= proc(n, p) local c, k; c, k:= 0, p;
       while n>=k do c:= c+iquo(n, k); k:= k*p od; c
    end:
a:= n-> min(seq(iquo(f(n, i[1]), i[2]), i=ifactors(n)[2])): a(1):=1:
seq(a(n), n=1..100);  # Alois P. Heinz, Oct 04 2012

Do[m = 1; While[ IntegerQ[ n!/n^m], m++ ]; Print[m - 1], {n, 1, 100} ]
HighestPower[n_,p_] := Module[{r,s=0,k=1}, While[r=Floor[n/p^k]; r>0, s=s+r; k++ ];s]; SetAttributes[HighestPower,Listable]; Join[{1}, Table[{p,e}=Transpose[FactorInteger[n]]; Min[Floor[HighestPower[n,p]/e]], {n,2,100}]] (* T. D. Noe, Oct 01 2008 *)
Join[{1},Table[IntegerExponent[n!,n],{n,2,500}]] (* Vladimir Joseph Stephan Orlovsky, Dec 26 2010 *)
f[n_, p_] := Module[{c=0, k=p}, While[n >= k , c = c + Quotient[n, k]; k = k*p ]; c]; a[1]=1; a[n_] := Min[ Table[ Quotient[f[n, i[[1]]], i[[2]]], {i, FactorInteger[n] }]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Oct 03 2013, after Alois P. Heinz's Maple program *)

a(n)=if(n>1, valuation(n!,n), 1); \\ Charles R Greathouse IV, Apr 10 2014

vp(n,p)=my(s); while(n\=p, s+=n); s
a(n)=if(n==1,return(1)); my(f=factor(n)); vecmin(vector(#f~, i, vp(n,f[i,1])\f[i,2])) \\ Charles R Greathouse IV, Apr 10 2014

A117494 a(n) is the number of m's, 1 <= m <= n, where gcd(m,n) is prime.

Original entry on oeis.org

0, 1, 1, 1, 1, 3, 1, 2, 2, 5, 1, 4, 1, 7, 6, 4, 1, 8, 1, 6, 8, 11, 1, 8, 4, 13, 6, 8, 1, 14, 1, 8, 12, 17, 10, 10, 1, 19, 14, 12, 1, 20, 1, 12, 14, 23, 1, 16, 6, 24, 18, 14, 1, 24, 14, 16, 20, 29, 1, 20, 1, 31, 18, 16, 16, 32, 1, 18, 24, 34, 1, 20, 1, 37, 28, 20, 16, 38, 1, 24, 18, 41, 1, 28

Offset: 1

Leroy Quet, Mar 22 2006

nonn

Dirichlet convolution of A000010 (Euler phi) and A010051 (characteristic function of primes), therefore also Möbius transform of A069359. - Antti Karttunen, Nov 17 2021

			Of the positive integers <= 12, exactly four (2, 3, 9 and 10) have a GCD with 12 that is prime. (gcd(2,12) = 2, gcd(3,12) = 3, gcd(9,12) = 3, gcd(10,12) = 2.)
So a(12) = 4.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A008683, A010051, A069359, A085548, A122410, A122411, A175787, A349338.

Coincides with A300251 on squarefree numbers, A005117.

a:=proc(n) local c,m: c:=0: for m from 1 to n do if isprime(gcd(m,n))=true then c:=c+1 else c:=c fi od: end: seq(a(n),n=1..100); # Emeric Deutsch, Apr 01 2006

f[n_] := Length@ Select[GCD[n, Range@n], PrimeQ@ # &]; Array[f, 84] (* Robert G. Wilson v, Apr 06 2006 *)
Table[Count[Range@ n, ?(PrimeQ@ GCD[#, n] &)], {n, 84}] (* _Michael De Vlieger, Feb 25 2018 *)
a[n_] := Module[{f = FactorInteger[n], p, e}, p = f[[;; , 1]]; e = f[[;; , 2]]; n * Times @@ (1-1/p) * Total[1/(p - (Boole[# == 1] & /@ e))]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jun 21 2025 *)

A117494(n) = sum(k=1,n,isprime(gcd(n,k))); \\ Antti Karttunen, Feb 25 2018

a(n) = my(f=factor(n)[, 1]); sum(k=1, #f, eulerphi(n/f[k])); \\ Daniel Suteu, Jun 23 2018

A117494(n) = sumdiv(n,d,eulerphi(n/d)*isprime(d)); \\ Antti Karttunen, Nov 17 2021

Dirichlet g.f: P(s)*Z(s-1)/Z(s) with P(s) the prime zeta function and Z(s) the Riemann zeta function. - Pierre-Louis Giscard, Jul 16 2014
a(n) = Sum_{distinct primes p dividing n} phi(n/p), where phi(k) is the Euler totient function. - Daniel Suteu, Jun 23 2018
From Antti Karttunen, Nov 17 2021: (Start)
a(n) = Sum_{d|n} A008683(n/d) * A069359(d).
a(n) = Sum_{d|n} A000010(n/d) * A010051(d).
a(n) = A349338(n) - A000010(n).
a(A005117(n)) = A300251(A005117(n)) for all n >= 1. (End)
a(n) = 1 iff n = 4 or n is prime (A175787). - Bernard Schott, Nov 18 2021
Sum_{k=1..n} a(k) ~ 3 * A085548 * n^2 / Pi^2. - Vaclav Kotesovec, Nov 20 2021

More terms from Emeric Deutsch, Apr 01 2006

A377484 a(n) = Product_{d|n, d>1} (d - 1).

Original entry on oeis.org

1, 1, 2, 3, 4, 10, 6, 21, 16, 36, 10, 330, 12, 78, 112, 315, 16, 1360, 18, 2052, 240, 210, 22, 53130, 96, 300, 416, 6318, 28, 146160, 30, 9765, 640, 528, 816, 1570800, 36, 666, 912, 560196, 40, 639600, 42, 27090, 39424, 990, 46, 37456650, 288, 42336, 1600, 45900, 52, 1874080, 2160

Offset: 1

Ridouane Oudra, Oct 29 2024

			a(12) = (2-1)*(3-1)*(4-1)*(6-1)*(12-1) = 1*2*3*5*11 = 330.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A007955, A020696.

Cf. A000079, A005329, A027871, A027872, A027875, A027879, A175787.

with(numtheory): seq(mul(d-1, d in divisors(n) minus {1}), n=1..80);

a[n_] := Times @@ (Rest@ Divisors[n] - 1); Array[a, 60] (* Amiram Eldar, Nov 01 2024 *)

a(n) = my(d=divisors(n)); prod(k=2, #d, d[k]-1); \\ Michel Marcus, Oct 30 2024

a(n) = Product_{k=2..A000005(n)} (A027750(n,k) - 1).
a(p^n) = Product_{k=1..n} (p^k - 1), where p is prime, and n an integer.
a(2^n) = A005329(n).
a(3^n) = A027871(n).
a(5^n) = A027872(n).
a(7^n) = A027875(n).
a(11^n) = A027879(n).
From Amiram Eldar, Nov 02 2024: (Start)
a(n) = n-1 if and only if n is in A175787 (i.e., n = 4 or n is prime).
a(n) == 1 (mod 2) if and only if n is a power of 2 (A000079). (End)

A226198 a(n) = floor((n-1)!/n).

Original entry on oeis.org

1, 0, 0, 1, 4, 20, 102, 630, 4480, 36288, 329890, 3326400, 36846276, 444787200, 5811886080, 81729648000, 1230752346352, 19760412672000, 336967037143578, 6082255020441600, 115852476579840000, 2322315553259520000, 48869596859895986086

Offset: 1

Vincenzo Librandi, May 31 2013

nonn

(h-1)!/h is integer if h belongs to A056653.

Vincenzo Librandi, Table of n, a(n) for n = 1..200

Cf. A001048 ((n+1)!/n), A056653, A091330 (floor((p-1)!/p), where p is prime), A175787 (prime numbers together with 4).

[Floor(Factorial(n-1)/n): n in [1..25]];

Mathematica
```
Table[Quotient[(n - 1)!, n], {n, 25}]
```

Edited by Bruno Berselli, May 31 2013

A331887 Number of partitions of n into distinct parts having a common factor > 1 with n.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 3, 1, 5, 1, 5, 4, 6, 1, 11, 1, 11, 6, 12, 1, 23, 3, 18, 8, 23, 1, 69, 1, 32, 13, 38, 7, 84, 1, 54, 19, 79, 1, 224, 1, 90, 46, 104, 1, 264, 5, 187, 39, 166, 1, 449, 14, 251, 55, 256, 1, 1374, 1, 340, 111, 390, 20, 1692, 1, 513, 105, 1610

Offset: 0

Ilya Gutkovskiy, Jan 30 2020

nonn

			a(12) = 5 because we have [12], [10, 2], [9, 3], [8, 4] and [6, 4, 2].

Antti Karttunen, Table of n, a(n) for n = 0..10416
Index entries for sequences related to partitions

Cf. A036998, A121998, A175787 (positions of 1's), A303280, A331885, A331888.

a:= proc(m) option remember; local b; b:=
      proc(n, i) option remember; `if`(i*(i+1)/21, b(n-i, min(i-1, n-i)), 0)+b(n, i-1)))
      end; forget(b); b(m$2)
    end:
seq(a(n), n=0..82);  # Alois P. Heinz, Jan 30 2020

Table[SeriesCoefficient[Product[(1 + Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 70}]

A331887(n) = { my(p = Ser(1, 'x, 1+n)); for(k=2, n, if(gcd(n,k)>1, p *= (1 + 'x^k))); polcoef(p, n); }; \\ Antti Karttunen, Jan 25 2025

a(n) = [x^n] Product_{k: gcd(n,k) > 1} (1 + x^k).

cp's OEIS Frontend

A161344 Numbers k with A033676(k)=2, where A033676 is the largest divisor <= sqrt(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A075254 a(n) = n + (sum of prime factors of n taken with repetition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

A011776 a(1) = 1; for n > 1, a(n) is defined by the property that n^a(n) divides n! but n^(a(n)+1) does not.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

A117494 a(n) is the number of m's, 1 <= m <= n, where gcd(m,n) is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A377484 a(n) = Product_{d|n, d>1} (d - 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A226198 a(n) = floor((n-1)!/n).

Views

Author

Keywords

Comments

Links

Crossrefs