A394475 Number of distinct primes not dividing n that are adjacent to a divisor of n.

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

Offset

1,4

Links

David A. Corneth, Table of n, a(n) for n = 1..10000

David A. Corneth, PARI program

Formula

From David A. Corneth, Apr 07 2026: (Start)

a(n) <= 2*A000005(n).

a(2*k + 1) = 1 for k >= 0. (End)

Example

   ------------------------------------------------
     n    Divisors      Adjacent Primes     a(n)
   ------------------------------------------------
     1      {1}              {2}             1
     2      {1,2}            {3}             1
     3      {1,3}            {2}             1
     4      {1,2,4}          {3,5}           2
     5      {1,5}            {2}             1
     6      {1,2,3,6}        {5,7}           2
     7      {1,7}            {2}             1
     8      {1,2,4,8}        {3,5,7}         3
     9      {1,3,9}          {2}             1
    10      {1,2,5,10}       {3,11}          2
    ...

Maple

f:= proc(n) local D;
   D:= NumberTheory:-Divisors(n);
   nops(select(isprime, (D +~ 1) union (D -~ 1) minus D))
end proc:
map(f, [$1..200]); # Robert Israel, Mar 22 2026

Mathematica

A394475[n_] := Count[Complement[Join[#+1, #-1], #], _?PrimeQ] & [Divisors[n]];
Array[A394475, 100] (* Paolo Xausa, May 03 2026 *)

Prog

(PARI) a(n) = my(nb=0); forprime(p=1, n+1, if ((!(n % (p-1)) || !(n % (p+1))) && (n % p), nb++)); nb; \\ Michel Marcus, Mar 22 2026
(PARI) \\ See Corneth link

Crossrefs

Cf. A000005, A395492.

Sequence in context: A359211 A072347 A368684 * A351034 A385482 A318831

Adjacent sequences: A394472 A394473 A394474 * A394478 A394479 A394480

Keyword

nonn

Author

Wesley Ivan Hurt, Mar 21 2026

Status

approved