A000430 -id:A000430 - cp's OEIS frontend

A181962 Numbers not of the form pi(p) + pi(sqrt(p)) for some prime p.

3, 6, 12, 19, 35, 45, 68, 80, 108, 156, 173, 231, 276, 297, 344, 425, 504, 537, 628, 695, 726, 833, 909, 1024, 1188, 1278, 1321, 1409, 1452, 1553, 1908, 2008, 2174, 2224, 2524, 2583, 2766, 2953, 3082, 3281, 3477, 3554, 3911, 3989, 4134, 4210, 4674, 5154, 5323

Offset: 1

Vladimir Shevelev, Apr 06 2012

nonn

Or places of squares in A000430.

			12 is in the sequence, since pi(23)+pi(sqrt(23))=9+2=11, while pi(29)+pi(sqrt(29))=10+3=13.
Also 12 is in the sequence since A000430(12)=25 is not prime.

Cf. A000430, A000040, A000720, A000879.

a:= n-> numtheory[pi](ithprime(n)^2)+n:
seq(a(n), n=1..50);  # Alois P. Heinz, Feb 21 2025

t = Table[PrimePi[n] + PrimePi[Sqrt[n]], {n, Prime[Range[10000]]}]; Complement[Range[t[[-1]]], t] (* T. D. Noe, Apr 09 2012 *)

from sympy import primepi, prime
def A181962(n): return primepi(prime(n)**2)+n # Chai Wah Wu, Feb 18 2025

a(n) = pi(prime(n)^2) + n = A000879(n) + n. - Chai Wah Wu, Feb 18 2025

A192489 Numbers m such that A099427(m) = 2.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 127, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157, 161, 163, 167, 169, 173, 175, 179

Offset: 1

Reinhard Zumkeller, Jul 02 2011

nonn

A099427(a(n)) = 2;
primes and squares of primes greater than 9 are subsequences, cf. A000040, A001248, A000430;
GCD(A099427(a(n)-1), A099427(a(n))) = 1;
a(n) = A038179(n) for n <= 22.
The next term divisible by 3 is a(137)=429. - Joe Slater, Jan 10 2017
All terms after the first are odd, since A099427(n) == n+1 (mod 2) for n >= 3. - Robert Israel, Jan 10 2017

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

a192489 n = a192489_list !! (n-1)
a192489_list = f 2 1 where
   f n x | x' == 2   = n : f (n+1) x'
         | otherwise = f (n+1) x'
         where x' = 1 + gcd n x

A099427:= proc(n) option remember; 1 + igcd(n,procname(n-1)) end proc:
A099427(1):= 1:
select(A099427=2, [$1..1000]); # Robert Israel, Jan 10 2017

(* b = A099427 *) b[1] = 1; b[n_] := b[n] = GCD[n, b[n - 1]] + 1;
Select[Range[200], b[#] == 2&] (* Jean-François Alcover, Mar 10 2019 *)

A293575 Difference between the number of proper divisors of n and the number of squares dividing n.

Original entry on oeis.org

-1, 0, 0, 0, 0, 2, 0, 1, 0, 2, 0, 3, 0, 2, 2, 1, 0, 3, 0, 3, 2, 2, 0, 5, 0, 2, 1, 3, 0, 6, 0, 2, 2, 2, 2, 4, 0, 2, 2, 5, 0, 6, 0, 3, 3, 2, 0, 6, 0, 3, 2, 3, 0, 5, 2, 5, 2, 2, 0, 9, 0, 2, 3, 2, 2, 6, 0, 3, 2, 6, 0, 7, 0, 2, 3, 3, 2, 6, 0, 6, 1, 2, 0, 9, 2, 2, 2, 5, 0, 9, 2, 3, 2, 2, 2, 8, 0, 3, 3, 4, 0, 6, 0, 5, 6

Offset: 1

Juri-Stepan Gerasimov, Oct 14 2017

sign

The difference between the number of ways of writing n = m + k and the number of ways of writing n = r*s, where m|k and r|s.

First occurrence of k beginning with k=-1: 1, 2, 8, 6, 12, 36, 24, 30, 72, 96, 60, 2097152, 216, 576, 120, 210, 1152, 240, 864, etc. - Robert G. Wilson v, Nov 28 2017

			a(6) = 2 because 2 is difference of number of ways of writing n = 1 + 5 = 2 + 4 = 3 + 3 where 1|5, 2|4, 3|3 and number of ways of writing n = 1*6 where 1|6.

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

One less than A056595.
Cf. A000430, A032741, A046951, A166684, A080257.
Cf. A001620, A013661.

f[n_] := Block[{d = Divisors@ n}, Length@ d - Length[ Select[ d, IntegerQ@ Sqrt@# &]] - 1];; Array[f, 105] (* Robert G. Wilson v, Nov 28 2017 *)

a(n) = A032741(n) - A046951(n).
a(n) = A056595(n) - 1. - Antti Karttunen, Oct 30 2017
a(n) = 0 iff n is a prime or a square of a prime, A000430. - Robert G. Wilson v, Nov 28 2017
Sum_{k=1..n} a(k) ~ n*log(n) + (2*gamma - zeta(2) - 2)*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Dec 01 2023

A325261 Numbers whose omega-sequence does not cover an initial interval of positive integers.

Original entry on oeis.org

8, 16, 24, 27, 30, 32, 36, 40, 42, 48, 54, 56, 64, 66, 70, 72, 78, 80, 81, 88, 96, 100, 102, 104, 105, 108, 110, 112, 114, 120, 125, 128, 130, 135, 136, 138, 144, 152, 154, 160, 162, 165, 168, 170, 174, 176, 180, 182, 184, 186, 189, 190, 192, 195, 196, 200

Offset: 1

Gus Wiseman, Apr 23 2019

nonn

We define the omega-sequence of n (row n of A323023) to have length A323014(n) = adjusted frequency depth of n, and the k-th term is Omega(red^{k-1}(n)), where Omega = A001222 and red^{k} is the k-th functional iteration of red = A181819, defined by red(n = p^i*...*q^j) = prime(i)*...*prime(j) = product of primes indexed by the prime exponents of n. For example, we have 180 -> 18 -> 6 -> 4 -> 3, so the omega-sequence of 180 is (5,3,2,2,1).

			The sequence of terms together with their omega sequences begins:
    8: 3->1           108: 5->2->2->1        189: 4->2->2->1
   16: 4->1           110: 3->3->1           190: 3->3->1
   24: 4->2->2->1     112: 5->2->2->1        192: 7->2->2->1
   27: 3->1           114: 3->3->1           195: 3->3->1
   30: 3->3->1        120: 5->3->2->2->1     196: 4->2->1
   32: 5->1           125: 3->1              200: 5->2->2->1
   36: 4->2->1        128: 7->1              208: 5->2->2->1
   40: 4->2->2->1     130: 3->3->1           210: 4->4->1
   42: 3->3->1        135: 4->2->2->1        216: 6->2->1
   48: 5->2->2->1     136: 4->2->2->1        222: 3->3->1
   54: 4->2->2->1     138: 3->3->1           224: 6->2->2->1
   56: 4->2->2->1     144: 6->2->2->1        225: 4->2->1
   64: 6->1           152: 4->2->2->1        230: 3->3->1
   66: 3->3->1        154: 3->3->1           231: 3->3->1
   70: 3->3->1        160: 6->2->2->1        232: 4->2->2->1
   72: 5->2->2->1     162: 5->2->2->1        238: 3->3->1
   78: 3->3->1        165: 3->3->1           240: 6->3->2->2->1
   80: 5->2->2->1     168: 5->3->2->2->1     243: 5->1
   81: 4->1           170: 3->3->1           246: 3->3->1
   88: 4->2->2->1     174: 3->3->1           248: 4->2->2->1
   96: 6->2->2->1     176: 5->2->2->1        250: 4->2->2->1
  100: 4->2->1        180: 5->3->2->2->1     252: 5->3->2->2->1
  102: 3->3->1        182: 3->3->1           255: 3->3->1
  104: 4->2->2->1     184: 4->2->2->1        256: 8->1
  105: 3->3->1        186: 3->3->1           258: 3->3->1

Complement of A325251.
Cf. A000430, A055932, A056239, A112798, A181819, A323023, A325247, A325260, A325262, A325277.
Omega-sequence statistics: A001222 (first omega), A001221 (second omega), A071625 (third omega), A323022 (fourth omega), A304465 (second-to-last omega), A182850 or A323014 (length/frequency depth), A325248 (Heinz number), A325249 (sum).

normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];
omseq[n_Integer]:=If[n<=1,{},Total/@NestWhileList[Sort[Length/@Split[#]]&,Sort[Last/@FactorInteger[n]],Total[#]>1&]];
Select[Range[100],!normQ[omseq[#]]&]

A338935 a(n) = Sum_{d|n} (d^2 mod n).

Original entry on oeis.org

0, 1, 1, 1, 1, 8, 1, 5, 1, 10, 1, 18, 1, 12, 20, 5, 1, 23, 1, 26, 17, 16, 1, 58, 1, 18, 10, 42, 1, 70, 1, 21, 32, 22, 40, 39, 1, 24, 23, 90, 1, 106, 1, 54, 71, 28, 1, 98, 1, 55, 44, 34, 1, 104, 37, 106, 29, 34, 1, 240, 1, 36, 77, 21, 65, 160, 1, 38, 56, 200, 1, 175, 1, 42, 60, 78, 94, 154, 1, 146

Offset: 1

J. M. Bergot and Robert Israel, Nov 16 2020

nonn

			a(6) = (1^2 mod 6) + (2^2 mod 6) + (3^2 mod 6) + (6^2 mod 6) = 1+4+3+0 = 8.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000430 (a(n)=1), A338930 (a(n) is prime).

f:= n -> add(t^2 mod n, t = numtheory:-divisors(n)):
map(f, [$1..100]);

Table[Total[Mod[Divisors[n]^2,n]],{n,80}] (* Harvey P. Dale, Oct 11 2021 *)

a(n) = sumdiv(n, d, lift(Mod(d, n)^2)); \\ Michel Marcus, Nov 16 2020

A087719 Least number m such that the number of numbers k <= m with k > spf(k)^n exceeds the number of numbers with k <= spf(k)^n.

Original entry on oeis.org

15, 27, 57, 135, 345, 927, 2577, 7335, 21225, 62127, 183297, 543735, 1618905, 4832127, 14447217, 43243335, 129533385, 388206927, 1163834337, 3489930135, 10466644665, 31393642527, 94168344657, 282479868135

Offset: 1

Reinhard Zumkeller, Sep 29 2003

nonn

mspf(k)^n & 1<=k<=m} <= m/2;

m>=a(n): #{k: k>spf(k)^n & 1<=k<=m} > m/2.

Cf. A088382, A088382, A088380, A088381, A000430, A080257.

Numbers so far satisfy a(n) = 3^n + 3*2^n + 6. - Ralf Stephan, May 10 2004

Empirical G.f.: 3*x*(5-21*x+20*x^2)/(1-x)/(1-2*x)/(1-3*x). - Colin Barker, Feb 22 2012

a(14)-a(24) from Giovanni Resta, May 23 2013

A089748 Numbers k that divide (sum of proper divisors of k + product of proper divisors of k).

Original entry on oeis.org

2, 6, 28, 120, 496, 672, 8128, 30240, 32760, 523776, 2178540, 23569920, 33550336, 45532800, 142990848, 459818240

Offset: 1

Joseph L. Pe, Jan 08 2004

All perfect numbers belong to this sequence.
Every term of A007691 is in this sequence. - T. D. Noe, Sep 29 2005
There are two sets of candidates of k: (i) k|A001065(k) and k|A007956(k) individually, or (ii) neither k|A001065(k) nor k|A007956(k) but the remainders of A001065(k)/k and A007956(k)/k sum up to k. If k has at least 4 divisors, the product of the second and penultimate divisor (in the sorted divisors list) is k, so k|A007956(k). This means for all k in A080257 we have k|A007956(k), and the k that do not divide A007956(k) are in A000430, which means k=p or k=p^2 for some prime p. If k=p, A001065(k)+A007956(k) = 1+1 =2, and the requirement here reduces to k|2 and only k=2 is left. If k=p^2, A001065(k) +A007956(k) = 1+p+p = 1+2*p, and the requirement here reduces to p^2 | (1+2*p), which has no solutions. This means case (ii) does not generate any solutions besides k=2. And this means all other solutions are from case (i), and therefore elements A007691 > 1 are the only remaining candidates. - R. J. Mathar, Oct 15 2021

Cf. A001065, A007956, A007691, A080257 (k which divide A007691(k)).

Cf. A219544.

isA087948 := proc(n)
    if modp( A001065(n)+A007956(n),n) = 0 then
        true;
    else
        false;
    end if;
end proc:
for n from 2 do
    if isA087948(n) then
        printf("%d\n",n) ;
    end if;
end do: # R. J. Mathar, Oct 15 2021

l = {}; Do[d = Drop[Divisors[n], -1]; p = Apply[Plus, d]; t = Apply[Times, d]; m = Mod[p + t, n]; If[m == 0, l = Append[l, n]], {n, 2, 10^6}]; l
Select[Range[2,22*10^5],Mod[Total[Most[Divisors[#]]]+Times@@Most[Divisors[#]],#]==0&] (* The program generates the first 11 terms of the sequence. *) (* Harvey P. Dale, Jun 05 2024 *)

from math import prod
from sympy import divisors
def ok(n): d = divisors(n)[:-1]; return n > 1 and (sum(d) + prod(d))%n == 0
print([k for k in range(10**5) if ok(k)]) # Michael S. Branicky, Oct 15 2021

a(11)-a(16) from Michael S. Branicky, Oct 16 2021

A186970 The oex analog of the Euler phi-function for the oex prime power factorization of positive integers.

Original entry on oeis.org

1, 1, 2, 3, 4, 3, 6, 4, 8, 5, 10, 7, 12, 8, 9, 12, 16, 11, 18, 12, 14, 14, 22, 9, 24, 16, 18, 18, 28, 13, 30, 16, 22, 21, 25, 24, 36, 24, 27, 17, 40, 17, 42, 30, 33, 29, 46, 27, 48, 32, 36, 36, 52, 24, 42, 25, 40, 37, 58, 28, 60, 40, 49, 48, 50, 30, 66, 48, 49, 35, 70, 32, 72, 48, 54, 54, 61, 36

Offset: 1

Vladimir Shevelev, Mar 01 2011

nonn

Oex divisors d of an integer n are defined in A186443: those divisors d which are either 1 or numbers such that d^k || n (the highest power of d dividing n) has odd exponent k.
A positive number is called an oex prime if it has only two oex divisors; since every n >= 2 has at least two oex divisors, 1 and n, an oex prime q has only oex divisors 1 and q. A000430 is the sequence of oex primes q, i.e., A186643(q) = 2 iff q is an entry in A000430.
A unique factorization, called an oex prime power factorization, of integers n is introduced as follows: each factor p^e in the conventional prime power factorization n = Product(p^e) is written as (p^2)^(e/2) if e is even, and as (p^2)^floor(e/2)*p if e is odd. This represents n as a product of oex primes of the type q=p^2, with unconstrained exponents e/2, and of oex primes of the type q=p with exponents 0 or 1. (This is similar to splitting n into its squarefree part A007913(n) times A008833(n), followed by an ordinary prime factorization in both parts separately.)
Let n = q_1^a_1*q_2^a_2*... and m = q_1^b_1*q_2^b_2*..., a_i,b_i >= 0 be the oex prime power factorizations of n and m. Define the oex GCD of n and m as [n,m] = q_1^min(a_1,b_1) * q_2^min(a_2,b_2) * .... Then a(n) = Sum_{m=1..n, [m,n]=1} 1, the oex analog of the Euler-phi function.

			The oex prime power factorization of 16 is 4^2. Since [16,i]=1 for i=1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, and 15, a(16)=12.
The oex prime power factorization of 9 is 9. Thus a(9)=8.

Cf. A000010, A000430, A186443, A186444, A186776, A064380.

highpp := proc(n,d) local nshf,a ; if n mod d <> 0 then 0; else nshf := n ; a := 0 ; while nshf mod d = 0 do nshf := nshf /d ; a := a+1 ; end do: a; end if; end proc:
oexgcd := proc(n,m) local a,p,kn,km ; a := 1 ; for p in numtheory[factorset](n) do kn := highpp(n,p) ; km := highpp(m,p) ; if type(kn,'even') = type(km,'even') then ; else kn := 2*floor(kn/2) ; km := 2*floor(km/2) ; end if; a := a*p^min(kn,km) ; end do: a ; end proc:
A186970 := proc(n) local a,i; a := 0 ; for i from 1 to n do if oexgcd(n,i) = 1 then a := a+1 ; end if; end do: a; end proc:
seq(A186970(n),n=1..80) ; # R. J. Mathar, Mar 18 2011

Let core(n) = p_1*...*p_r = A007913(n), n/core(n) = A008833(n) = q_1^c_1*...*q_t^c_t, where q_i are squares of primes.
If core(n)=1, then a(n) = n*Product_{j=1..r} (1-1/q_i); if core(n) tends to infinity, then a(n) ~ n * core(n) * Product_{i=1..t} (1-1/q_i) / Product_{j=1..r} (1+p_j).
a(n) <= A064380(n).

A280619 Integers m such that sigma(m) - eulerphi(m) <= 4*sqrt(m).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241

Offset: 1

Michel Marcus, Jan 06 2017

Equals {1, 8} union A000430 (primes and square of primes).

Equals 8 union A166684.

Indranil Ghosh, Table of n, a(n) for n = 1..10000
Mathematical Reflections, Solution to Problem O261, Issue 3, 2013, p. 24.

A000430 is the main entry for this sequence.

Cf. A000010, A000203, A166684.

Select[Range[250],DivisorSigma[1,#]-EulerPhi[#]<=4Sqrt[#]&] (* Harvey P. Dale, Jul 10 2018 *)

isok(n) = sigma(n) - eulerphi(n) <= 4*sqrt(n); \\ Michel Marcus, Jan 06 2017

A307360 A sequence in which every divisor other than 1 is used at most three times.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229

Offset: 1

Joshua R. Tint, Apr 04 2019

In other words, for every k > 1, there are at most 3 multiples of k in the sequence. - Rémy Sigrist,  Apr 08 2019
The sequence begins at 1. The smallest integer greater than the last term which is not divisible by a divisor already used three times (excluding one) is added to the sequence.
Contains all prime numbers (A000040), given that the prime numbers only have the divisors of themselves and one, by definition, therefore the only divisor which could exist in the sequence already to disqualify the number from inclusion in the sequence would be the prime number itself, but a number cannot have a divisor higher than itself (the prime numbers), so given that the sequence increases, the divisor could not exist in the sequence, and any prime number would be included.
Terms are {1} or primes or squares of primes (A000430) or numbers of the form prime(2k + 1) * prime(2k + 2) (A089581) where k >= 0. - David A. Corneth, Apr 09 2019

			For instance, 8 is not in the sequence because 2, 4, and 6 are all divisible by 2 and appear previously in the sequence. The sequence, then, skips to nine. After 9, no more numbers divisible by three appear in the sequence, given that after 3 and 6, it is the third number divisible by three to appear in the sequence.

Robert Israel, Table of n, a(n) for n = 1..10000
Aaron Greicius, The Prime Numbers, Lecture Fall 2012.

See A166684 for the variant in which every divisor other than one is used at most twice.

Union of {1}, A000430 and A089581.

N:= 1000: # for terms <= N
M:= Vector(N):
Candidates:= {$2..N}:
A[1]:= 1:
for n from 2 while Candidates <> {} do
  A[n]:= min(Candidates):
  Candidates:= Candidates minus {A[n]};
  for d in numtheory:-divisors(A[n]) minus {1} do
     M[d]:= M[d]+1;
     if M[d] = 3 then Candidates:= Candidates minus {seq(i,i=2*d..N, d)} fi;
  od;
od:
seq(A[i],i=1..n-1); # Robert Israel, Apr 09 2019

Select[Range@ 229, Or[# == 1, PrimeQ@ #, PrimeQ@ Sqrt@ #, And[SquareFreeQ@ #, If[PrimeNu@ # == 2, And[OddQ@ First@ #, Apply[SameQ, (# - {1, 2})/2]] &@ PrimePi[FactorInteger[#][[All, 1]]], False]]] &] (* Michael De Vlieger, Apr 11 2019 *)

is(n) = if(n==1, return(1)); my(f=factor(n)); if(f[, 2] == [1]~ || f[, 2] ==[2]~, return(1)); if(f[,2] == [1,1]~ && nextprime(f[1,1]+1) == f[2,1] && primepi(f[1,1]) % 2 == 1, return(1)); 0 \\ David A. Corneth, Apr 09 2019

More terms from Jinyuan Wang, Apr 07 2019

cp's OEIS Frontend

A181962 Numbers not of the form pi(p) + pi(sqrt(p)) for some prime p.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A192489 Numbers m such that A099427(m) = 2.

Views

Author

Keywords

Comments

Links

Programs

Haskell

Maple

Mathematica

A293575 Difference between the number of proper divisors of n and the number of squares dividing n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A325261 Numbers whose omega-sequence does not cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A338935 a(n) = Sum_{d|n} (d^2 mod n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A087719 Least number m such that the number of numbers k <= m with k > spf(k)^n exceeds the number of numbers with k <= spf(k)^n.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A089748 Numbers k that divide (sum of proper divisors of k + product of proper divisors of k).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A186970 The oex analog of the Euler phi-function for the oex prime power factorization of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs