A000430 -id:A000430 - cp's OEIS frontend

A332306 a(n) is the least k such that A121663(k) = n.

0, 1, 2, 4, 8, 3, 32, 5, 128, 9, 512, 6, 2048, 33, 10, 65, 32768, 18, 131072, 12, 34, 513, 2097152, 7, 8388608, 2049, 130, 36, 134217728, 11, 536870912, 68, 514, 32769, 40, 19, 34359738368, 131073, 2050, 13, 549755813888, 35, 2199023255552, 516, 136, 2097153

Offset: 1

Rémy Sigrist, Feb 09 2020

The binary representation of a(n) encodes the colexicographically earliest factorization of n into distinct factors greater than 1.

			The first terms, alongside their binary representations and factorizations, are:
  n   a(n)    bin(a(n))           Factorization
  --  ------  ------------------  -------------
   1       0                   0
   2       1                   1              2
   3       2                  10              3
   4       4                 100              4
   5       8                1000              5
   6       3                  11            2*3
   7      32              100000              7
   8       5                 101            2*4
   9     128            10000000              9
  10       9                1001            2*5
  11     512          1000000000             11
  12       6                 110            3*4
  13    2048        100000000000             13
  14      33              100001            2*7
  15      10                1010            3*5
  16      65             1000001            2*8
  17   32768    1000000000000000             17
  18      18               10010            3*6
  19  131072  100000000000000000             19
  20      12                1100            4*5

Rémy Sigrist, PARI program for A332306

Cf. A000430, A045778, A121663.

PARI
```
See Links section.
```

a(n) = 2^(n-2) iff n is a prime number of the square of a prime number (A000430).
a(n!) = 2^(n-1)-1 for any n > 0.
a(p_1*...*p_k) = 2^(p_1-2)+...+2^(p_k-2) for distinct prime numbers p_1, ..., p_k.

A337868 Number of distinct residues of x^r (mod n), x=0..n-1, r=2, ..., n.

Original entry on oeis.org

0, 2, 3, 3, 5, 6, 7, 6, 7, 10, 11, 9, 13, 14, 15, 11, 17, 14, 19, 15, 21, 22, 23, 17, 21, 26, 20, 21, 29, 30, 31, 21, 33, 34, 35, 21, 37, 38, 39, 28, 41, 42, 43, 33, 35, 46, 47, 32, 43, 42, 51, 39, 53, 40, 55, 39, 57, 58, 59, 45, 61, 62, 49, 41, 65, 66, 67, 51, 69, 70, 71

Offset: 1

José María Grau Ribas, Sep 27 2020

nonn

Sequence is submultiplicative: a(m*n) <= a(m) * a(n) for m,n coprime. - Charles R Greathouse IV, Dec 19 2022

For n > 1, this is the number of distinct residues of x^r (mod n) with r > 1, that is, the restriction r <= n is not needed. - Charles R Greathouse IV, Dec 22 2022

For number of k-th power residues mod n, see A000224 (k=2), A052273 (k=4), A052274 (k=5), A052275 (k=6), A085310 (k=7), A085311 (k=8), A085312 (k=9), A085313 (k=10), A085314 (k=12), A228849 (k=13).

T[n_] := Union@Mod[Flatten@Table[Range[n]^i, {i, 2, n}], n];
Table[Length[T@n], {n, 1, 144}]

a(n)=if(n==1, return(0)); my(s); for(k=0,n-1, my(x=Mod(k,n)); forprime(p=2,n, if(ispower(x,p), s++; break))); s\\ Charles R Greathouse IV, Dec 22 2022

For n > 1, a(n) >= A000010(n) + 1 as all invertible elements of Z/nZ are powers, as is 0. (Conjecture: equality holds exactly for A000430, the primes and squares of primes.) - Charles R Greathouse IV, Dec 23 2022

A340768 Third-smallest divisor of n-th composite number.

Original entry on oeis.org

4, 3, 4, 9, 5, 3, 7, 5, 4, 3, 4, 7, 11, 3, 25, 13, 9, 4, 3, 4, 11, 17, 7, 3, 19, 13, 4, 3, 4, 5, 23, 3, 49, 5, 17, 4, 3, 11, 4, 19, 29, 3, 31, 7, 4, 13, 3, 4, 23, 5, 3, 37, 5, 4, 11, 3, 4, 9, 41, 3, 17, 43, 29, 4, 3, 13, 4, 31, 47, 19, 3, 7, 9, 4, 3, 4, 5, 53

Offset: 1

Charles Kusniec, Jan 20 2021

The terms are either primes or squares of primes.

Cf. A020639, A000290, A000040, A002808, A001248, A000430.

f[n_] := Divisors[n][[3]]; f /@ Select[Range[100], CompositeQ] (* Amiram Eldar, Jan 20 2021 *)

lista(nn)=my(list = List()); forcomposite(n=1, nn, listput(list, divisors(n)[3]);); Vec(list); \\ Michel Marcus, Jan 20 2021

do(lim)=my(v=List()); forfactored(n=4,lim\1, my(f=n[2]); if(#f~==1, if(f[1,2]>1, listput(v,f[1,1]^2)), listput(v, if(f[1,2]>1, min(f[1,1]^2,f[2,1]), f[2,1])))); Vec(v) \\ Charles R Greathouse IV, Nov 17 2022

from sympy import divisors, composite
def A340768(n):
    return divisors(composite(n))[2] # Chai Wah Wu, Jan 21 2021

A340769 The third-smallest divisor of n-th square number, n>1.

Original entry on oeis.org

4, 9, 4, 25, 3, 49, 4, 9, 4, 121, 3, 169, 4, 5, 4, 289, 3, 361, 4, 7, 4, 529, 3, 25, 4, 9, 4, 841, 3, 961, 4, 9, 4, 7, 3, 1369, 4, 9, 4, 1681, 3, 1849, 4, 5, 4, 2209, 3, 49, 4, 9, 4, 2809, 3, 11, 4, 9, 4, 3481, 3, 3721, 4, 7, 4, 13, 3, 4489, 4, 9, 4, 5041, 3

Offset: 2

Charles Kusniec, Jan 20 2021

nonn

The terms are either primes or squares of primes.

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

Cf. A020639, A000290, A000040, A001248, A000430.

f:= proc(n) local F,t;
  F:= sort(ifactors(n)[2],(a,b) -> a[1]= 2 and F[2,1] < F[1,1]^2 then F[2,1] else F[1,1]^2 fi
end proc:
map(f, [$2..100]); # Robert Israel, Oct 09 2024

a[n_] := Divisors[n^2][[3]]; Array[a, 100, 2] (* Amiram Eldar, Jan 20 2021 *)

a(n) = divisors(n^2)[3]; \\ Michel Marcus, Jan 20 2021

A277187 Numbers n such that A001158(n) == 1 (mod n).

Original entry on oeis.org

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

Offset: 1

Ilya Gutkovskiy, Oct 04 2016

Essentially the same as A087797. - Ilya Gutkovskiy, Dec 26 2016

			a(1) = 2 because sigma_3(2) = 1^3 + 2^3 = 9 and 9 == 1 (mod 2);
a(2) = 3 because sigma_3(3) = 1^3 + 3^3 = 28 and 28 == 1 (mod 3);
a(3) = 4 because sigma_3(4) = 1^3 + 2^3 + 4^3 = 73 and 73 == 1 (mod 4), etc.

Cf. A000040, A000430, A001158, A001248, A030078, A087797.

Select[Range[300], Mod[DivisorSigma[3, #1], #1] == 1 & ]

Edited by Ilya Gutkovskiy, Dec 26 2016

A337176 Number of pairs of divisors of n, (d1,d2), such that d1 <= d2 and d1*d2 < sqrt(n).

Original entry on oeis.org

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

Offset: 1

Wesley Ivan Hurt, Jan 28 2021

nonn

a(n) = 1 iff n is prime or n is the square of a prime (A000430). - Bernard Schott, Jan 30 2021

			a(24) = 5; (1,1), (1,2), (1,3), (1,4), (2,2).
a(25) = 1; (1,1).
a(26) = 3; (1,1), (1,2), (2,2).
a(27) = 2; (1,1), (1,3).

Cf. A337175.

Table[Sum[Sum[(1 - Sign[Floor[(i*k)/Sqrt[n]]]) (1 - Ceiling[n/k] + Floor[n/k]) (1 - Ceiling[n/i] + Floor[n/i]), {i, k}], {k, n}], {n, 80}]

a(n) = Sum_{d1|n, d2|n} (1 - sign(floor(d1*d2/sqrt(n)))).

A337177 Sum of the divisors d of n such that d is not equal to n/d.

Original entry on oeis.org

0, 3, 4, 5, 6, 12, 8, 15, 10, 18, 12, 28, 14, 24, 24, 27, 18, 39, 20, 42, 32, 36, 24, 60, 26, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 85, 38, 60, 56, 90, 42, 96, 44, 84, 78, 72, 48, 124, 50, 93, 72, 98, 54, 120, 72, 120, 80, 90, 60, 168, 62, 96, 104, 119, 84, 144, 68, 126

Offset: 1

Wesley Ivan Hurt, Jan 28 2021

a(n) = n+1 iff n is prime or n is the square of a prime (A000430). - Bernard Schott, Jan 29 2021

Cf. A000203, A037213 (with equal instead of not equal).

Table[Sum[k*(1 - KroneckerDelta[k, n/k]) (1 - Ceiling[n/k] + Floor[n/k]), {k, n}], {n, 80}]

a(n) = sumdiv(n, d, d*(d!=n/d)); \\ Michel Marcus, Jan 29 2021

a(n) = sigma(n) - issquare(n)*sqrtint(n) \\ David A. Corneth, Jan 30 2021

a(n) = Sum_{d|n} d * (1 - [d = n/d]), where [ ] is the Iverson bracket.

a(n) = sigma(n) - A037213(n). - David A. Corneth, Jan 30 2021

A383505 Least integer k >= 0 such that binomial(k*n,k+1) = -1 mod n, or -1 if no such integer exists.

Original entry on oeis.org

0, 1, 2, 3, 4, 341, 6, 79, 8, 19599, 10, 3937027727, 12, 2841, 22679, 47, 16, 18459448019, 18, 179, 146, 4003647, 22, 77934182399, 24, 299519, 80, 29952579, 28

Offset: 1

Jason Bard, May 05 2025

Conjecture: a(A000430(n)) = A000430(n)-1.
It is not hard to see that conjecture is true. - Max Alekseyev, Jul 24 2025
Other values calculated: a(32) = 1343, a(34) = 1121, a(38) = 417.
If exists, a(30) > 10^13. - Max Alekseyev, Jul 24 2025

			a(6) = 341 because binomial(341*6, 341+1) = 5 mod 6, and no smaller nonnegative integer satisfies this.

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems: Binomial coefficients modulo integers (binomod.gp).

Cf. A000430, A059288, A099905.

f = {}; Do[k = 0; While[! Mod[Binomial[k*n, k + 1], n] == n - 1, k++]; f = Join[f, {k}], {n, 1, 11}]

a(n) = my(k=0); while (binomod(k*n,k+1, n) != Mod(-1, n), k++); k; \\ Michel Marcus, May 10 2025

If p is prime, then a(p) = p-1 by Lucas' theorem. - Chai Wah Wu, Jul 21 2025

a(12) from Chai Wah Wu, Jul 21 2025

a(18), a(22), a(24), a(26), a(28) from Max Alekseyev, Jul 24 2025

cp's OEIS Frontend

A332306 a(n) is the least k such that A121663(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A337868 Number of distinct residues of x^r (mod n), x=0..n-1, r=2, ..., n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A340768 Third-smallest divisor of n-th composite number.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

PARI

Python

A340769 The third-smallest divisor of n-th square number, n>1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A277187 Numbers n such that A001158(n) == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A337176 Number of pairs of divisors of n, (d1,d2), such that d1 <= d2 and d1*d2 < sqrt(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A337177 Sum of the divisors d of n such that d is not equal to n/d.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A383505 Least integer k >= 0 such that binomial(k*n,k+1) = -1 mod n, or -1 if no such integer exists.

Views

Author

Keywords

Comments