A123317 Smallest prime power m such that n+m is a prime number.

1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 8, 5, 4, 3, 2, 1, 2, 1, 16, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 32, 5, 4, 3, 2, 1, 8, 5, 4, 3, 2, 1, 2, 1, 256, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 16, 5, 4, 3, 2, 1, 4, 3, 2, 1, 128, 5, 4, 3, 2, 1, 8, 7, 16, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1

Offset: 1

Author

Reinhard Zumkeller, Sep 27 2006

Keywords

• nonn

Examples

			n=23: 23+1=3*2^3, 23+2=5^2, 23+3=13*2, 23+2^2=3^3, 23+5=7*2^2, 23+7=5*3*2, but 23+8=31=A000040(11), therefore a(23)=8;
n=24: 24+1=5^2, 24+2=13*2, 24+3=3^3, 24+2^2=7*2^2, but 24+5=29=A000040(10), therefore a(24)=5;
the smallest occurring proper odd prime power is 9=3^2:
n=118: 118+1=17*7, 118+2=5*3*2^3, 118+3=11^2, 118+2^2=61*2, 118+5=41*3, 118+7=5^3, 118+2^3=7*2*3^2, but 118+3^2=127=A000040(31), therefore a(118)=9.
		

Crossrefs

Cf. A013632, A000961.

Programs

Maple

A123317 := proc(n)
    local m ;
    m :=1 ;
    if isprime(n+m) then
        return m ;
    end if;
    for m from 2 do
        if nops(numtheory[factorset](m)) = 1 then
            if isprime(n+m) then
                return m;
            end if;
        end if;
    end do:
end proc:
seq(A123317(n),n=1..102) ; # R. J. Mathar, Aug 09 2019

Formula

A123318(n) = n + a(n);

a(A006093(n)) = 1; a(A040976(n)) = 2 for n>2.