Finding The nth Prime such that the prime - 1 is divisible by n

Problem

The goal is as the title says to find the $$\n\$$th prime such that $$\\text{the prime}-1\$$ is divisible by $$\n\$$.

Explanation

Here is an example so you understand the question, this is not necessarily the way it ought to be solved. It merely as a way to explain the question

given $$\3\$$ as an input we would first look at all the primes

 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 ...


Then we select the primes such that $$\\text{the prime}-1\$$ is divisible by $$\n\$$ (3 in this case)

 7 13 19 31 37 43 61 67 73 79 97 103 107 109 127 ...


We then select the $$\n\$$th term in this sequence

We would output $$\19\$$ for an input of $$\3\$$

Note

We can also think of this as the $$\n\$$th prime in the sequence $$\\{1, n + 1, 2n + 1, 3n + 1 ...kn + 1\}\$$ where $$\k\$$ is any natural number

Test Cases

  1 --> 2
2 --> 5
3 --> 19
4 --> 29
100 --> 39301
123 --> 102337

• You say Nth prime [...] divisible by n. Are N and n the same number? Commented Nov 17, 2016 at 3:09
• Sorry, Yeah, they are the same, I should have fixed it now Commented Nov 17, 2016 at 3:11
• A077317 Commented Nov 17, 2016 at 3:11
• You might want to add 1 -> 2 to the test cases. One of my answers got it wrong at some point. Commented Nov 17, 2016 at 4:04
• Another way to phrase this is "find the nth prime in the arithmetic sequence 1,n+1,2n+1,...,kn+1,... (which sequence is guaranteed to have infinitely many primes by Dirichlet's Thm.). Commented Nov 17, 2016 at 16:48

05AB1E, 9 8 bytes

05AB1E uses CP-1252 encoding.

Saved a byte thanks to Osable

µN¹*>Dp½


Try it online!

Explanation

µ          # for N in [1 ...] loop until counter == input
N¹*>      # N*input+1 (generate multiples of input and increment)
D     # duplicate
p½   # if prime, increase counter
# implicitly output last prime

• Instead of bruteforcing I would suggest generating multiples of N first and then checking if they are primes. I came up with µN¹*>Dp½ which saves one byte and accelerates the computation. Commented Nov 17, 2016 at 10:30
• @Osable: Ah of course! That is indeed a much better approach. Thanks :) Commented Nov 17, 2016 at 10:32

Python 2, 58 bytes

n=N=input();m=k=1
while N:m*=k*k;k+=1;N-=m%k>~-k%n
print k


Mathematica, 48 bytes

Select[Array[Prime,(n=#)^3],Mod[#-1,n]==0&][[n]]&


Unnamed function taking a single argument, which it names n. Generates a list of the first n^3 primes, selects the ones that are congruent to 1 modulo n, then takes the nth element of the result. It runs in several seconds on the input 123.

It's not currently known if there's always even a single prime, among the first n^3 primes, that is congruent to 1 modulo n, much less n of them. However, the algorithm can be proved correct (at least for large n) under the assumption of the generalized Riemann hypothesis!

f n=[p|p<-[1,n+1..],all((<2).gcd p)[2..p-1]]!!n


Usage example: f 4 -> 29.

How it works:

[p|p<-[1,n+1..]                     ]    -- make a list of all multiples of n+1
-- (including 1, as indexing is 0-based)
,all((<2).gcd p)[2..p-1]      -- and keep the primes
!!n       -- take the nth element


Edit: Thanks @Damien for 12 bytes by removing the divisibility test and only looking at multiples in the first place.

• f n=[p|p<-[1,n+1..],all((<2).gcd p)[2..p-1]]!!n Commented Nov 17, 2016 at 10:19
• @Damien: wow, a byte save of 20%. Thanks a lot!
– nimi
Commented Nov 17, 2016 at 15:14

Jelly, 9 bytes

‘ÆP>%ð#Ṫ‘


Try it online!

How it works

‘ÆP>%ð#Ṫ‘  Main link. Argument: n

ð#    Call the dyadic chain to the left with right argument n and left
argument k = n, n+1, n+2, ... until n of them return 1.
‘          Increment; yield k+1.
ÆP        Test k+1 for primality, yielding 1 or 0.
%      Compute k%n.
>       Compare the results to both sides, yielding 1 if and only if k+1 is
prime and k is divisible by n.
Ṫ   Tail; extract the last k.
‘  Increment; yield k+1.


Java 7, 106 bytes

int c(int n){for(int z=1,i=2,j,x;;i++){x=i;for(j=2;j<x;x=x%j++<1?0:x);if(x>1&(i-1)%n<1&&z++==n)return i;}}


Ungolfed:

int c(int n){
for(int z = 1, i = 2, j, x; ; i++){
x = i;
for(j = 2; j < x; x = x % j++ < 1
? 0
: x);
if(x > 1 & (i-1) % n < 1 && z++ == n){
return i;
}
}
}


Test code:

Try it here (last test case results in a Time limit exceeded on ideone)

class M{
static int c(int n){for(int z=1,i=2,j,x;;i++){x=i;for(j=2;j<x;x=x%j++<1?0:x);if(x>1&(i-1)%n<1&&z++==n)return i;}}

public static void main(String[] a){
System.out.println(c(1));
System.out.println(c(2));
System.out.println(c(3));
System.out.println(c(4));
System.out.println(c(100));
System.out.println(c(123));
}
}


Output:

2
5
19
29
39301
102337

• Nice to see the ungolfed code for comparison, but the tests would need to be on the golfed code to be meaningful... Commented Nov 17, 2016 at 13:37
• @trichoplax Well, I always post the full test program at the Ungolfed & test code part of my answers. The System.out.println are mostly added so you see what input I've used to give the shown output, and everything is also given in case anyone wants to copy-paste it in their IDE to play around with. Commented Nov 17, 2016 at 13:46
• My comment wasn't intended terribly seriously - it just might make some people think you had only tested the code before golfing. You could always have three sections: Golfed, Ungolfed, and Golfed with test code, if you wanted to head off that assumption... Commented Nov 17, 2016 at 14:58
• @trichoplax Ah ok, In that case it's indeed a justified and good comment. :) I'll edit this one, and keep it in mind for future challenges. Commented Nov 17, 2016 at 15:02

Nasm 679 bytes (Instruction Intel 386 cpu 120 bytes)

isPrime1:
push ebp
mov ebp,dword[esp+ 8]
mov ecx,2
mov eax,ebp
cmp ebp,1
ja .1
.n: xor eax,eax
jmp short .z
.1: xor edx,edx
cmp ecx,eax
jae .3
div ecx
or edx,edx
jz .n
mov ecx,3
mov eax,ebp
.2: xor edx,edx
cmp ecx,eax
jae .3
mov eax,ebp
div ecx
or edx,edx
jz .n
inc ecx
inc ecx
jmp short .2
.3: xor eax,eax
inc eax
.z: pop   ebp
ret 4
Np:
push esi
push edi
mov esi,dword[esp+ 12]
xor edi,edi
or esi,esi
ja .0
.e: xor eax,eax
jmp short .z
.0: inc esi
jz .e
push esi
call isPrime1
dec esi
cmp edi,dword[esp+ 12]
jae .1
jc .e
jmp short .0
.1: mov eax,esi
inc eax
.z: pop edi
pop esi
ret 4


this is ungolfed one and the results

;0k,4ra,8Pp
isPrime1:
push    ebp
mov     ebp,  dword[esp+  8]
mov     ecx,  2
mov     eax,  ebp
cmp     ebp,  1
ja      .1
.n:       xor     eax,  eax
jmp     short  .z
.1:       xor     edx,  edx
cmp     ecx,  eax
jae     .3
div     ecx
or      edx,  edx
jz      .n
mov     ecx,  3
mov     eax,  ebp
.2:       xor     edx,  edx
cmp     ecx,  eax
jae     .3
mov     eax,  ebp
div     ecx
or      edx,  edx
jz      .n
inc     ecx
inc     ecx
jmp     short  .2
.3:       xor     eax,  eax
inc     eax
.z:
pop     ebp
ret     4

; {1, n+1, 2n+1, 3n+1 }
; argomento w, return il w-esimo primo nella successione di sopra
;0j,4i,8ra,12P
Np:
push    esi
push    edi
mov     esi,  dword[esp+  12]
xor     edi,  edi
or      esi,  esi
ja      .0
.e:       xor     eax,  eax
jmp     short  .z
.0:       inc     esi
jz      .e
push    esi
call    isPrime1
dec     esi
cmp     edi,  dword[esp+  12]
jae     .1
jc      .e
jmp     short  .0
.1:       mov     eax,  esi
inc     eax
.z:
pop     edi
pop     esi
ret     4

00000975  55                push ebp
00000976  8B6C2408          mov ebp,[esp+0x8]
0000097A  B902000000        mov ecx,0x2
0000097F  89E8              mov eax,ebp
00000981  81FD01000000      cmp ebp,0x1
00000987  7704              ja 0x98d
00000989  31C0              xor eax,eax
0000098B  EB28              jmp short 0x9b5
0000098D  31D2              xor edx,edx
0000098F  39C1              cmp ecx,eax
00000991  731F              jnc 0x9b2
00000993  F7F1              div ecx
00000995  09D2              or edx,edx
00000997  74F0              jz 0x989
00000999  B903000000        mov ecx,0x3
0000099E  89E8              mov eax,ebp
000009A0  31D2              xor edx,edx
000009A2  39C1              cmp ecx,eax
000009A4  730C              jnc 0x9b2
000009A6  89E8              mov eax,ebp
000009A8  F7F1              div ecx
000009AA  09D2              or edx,edx
000009AC  74DB              jz 0x989
000009AE  41                inc ecx
000009AF  41                inc ecx
000009B0  EBEE              jmp short 0x9a0
000009B2  31C0              xor eax,eax
000009B4  40                inc eax
000009B5  5D                pop ebp
000009B6  C20400            ret 0x4
68

000009B9  56                push esi
000009BA  57                push edi
000009BB  8B74240C          mov esi,[esp+0xc]
000009BF  31FF              xor edi,edi
000009C1  09F6              or esi,esi
000009C3  7704              ja 0x9c9
000009C5  31C0              xor eax,eax
000009C7  EB1D              jmp short 0x9e6
000009C9  46                inc esi
000009CA  74F9              jz 0x9c5
000009CC  56                push esi
000009CD  E8A3FFFFFF        call 0x975
000009D4  4E                dec esi
000009D5  3B7C240C          cmp edi,[esp+0xc]
000009D9  7308              jnc 0x9e3
000009DF  72E4              jc 0x9c5
000009E1  EBE6              jmp short 0x9c9
000009E3  89F0              mov eax,esi
000009E5  40                inc eax
000009E6  5F                pop edi
000009E7  5E                pop esi
000009E8  C20400            ret 0x4
000009EB  90                nop
120

[0, 0] [1, 2] [2, 5] [3, 19] [4, 29] [5, 71] [6, 43] [7, 211] [8, 193] [9, 271] [1
0, 191] [11, 661] [12, 277] [13, 937] [14, 463] [15, 691] [16, 769] [17, 1531] [18
, 613] [19, 2357] [20, 1021] [21, 1723] [22, 1409] [23, 3313] [24, 1609] [25, 3701
] [26, 2029] [27, 3187] [28, 2437] [29, 6961] [30, 1741] [31, 7193] [32, 3617] [33
, 4951] [34, 3877] [35, 7001] [36, 3169] [37, 10657] [38, 6271] [39, 7879] [40, 55
21] [41, 13613] [42, 3823] [43, 15137] [44, 7349] [45, 9091] [46, 7499] [47, 18049
] [48, 6529] [49, 18229] [50, 7151] [51, 13159] [52, 10141] [53, 26501] [54, 7669]
[55, 19801] [56, 11593] [57, 18127] [58, 13109] [59, 32569] [60, 8221] [61, 34649
] [62, 17981] [63, 21799] [64, 16001] [65, 28081] [66, 10429] [67, 39799] [68, 193
81] [69, 29947] [70, 14771] [71, 47713] [72, 16417] [73, 51539] [74, 25013] [75, 2
9101] [76, 26449] [77, 50051] [78, 16927] [79, 54037] [80, 23761] [81, 41149] [82,
31489] [83, 68891] [84, 19237] [85, 51341] [86, 33713] [87, 45589] [88, 34057] [8
9, 84551] [90, 19531] [91, 64793] [92, 42689] [93, 54499] [94, 41737] [95, 76001]
[96, 27457] [97, 97583] [98, 40867] [99, 66529] [100, 39301] [101, 110899] [102, 2
9989] [103, 116803] [104, 49297] [105, 51871] [106, 56711] [107, 126047] [108, 385
57] [109, 133853] [110, 42901] [111, 76369] [112, 53089] [113, 142607] [114, 40129
] [115, 109481] [116, 63337] [117, 83071] [118, 67733] [119, 112337] [120, 41281]
[121, 152219] [122, 70639] [123, 102337]


Actually, 13 bytes

Golfing suggestions welcome! Try it online!

;╗PD╜@%Y╓NP


Ungolfing

         Implicit input n.
;╗       Save a copy of n to register 0.
...╓   Push first n values where f(x) is truthy, starting with f(0).
PD       Get the x-th prime - 1.
╜@%      Push (x_p - 1) % n.
Y        If x_p-1 is divisible by n, return 1. Else, return 0.
NP       Get the n-th prime where n_p-1 is divisible by n.
Implicit return.


Common Lisp, 162 bytes

(defun s(n)(do((b 2(loop for a from(1+ b)when(loop for f from 2 to(1- a)never(=(mod a f)0))return a))(a 0)(d))((= a n)d)(when(=(mod(1- b)n)0)(incf a)(setf d b))))


Usage:

* (s 100)

39301


Ungolfed:

(defun prime-search (n)
(do ((prime 2 (loop for next from (1+ prime) when
(loop for factor from 2 to (1- next) never
(= (mod next factor) 0)) return next))
(count 0) (works))
((= count n) works)
(when (= (mod (1- prime) n) 0)
(incf count)
(setf works prime))))


Some of those loop constructs can probably be shortened into do loops, but this is what I've got for now.

MATL, 12 bytes

1i:"_YqtqG\


Try it online!

(For input 123 it times out in the online compiler, but it works offline.)

Explanation

1          % Push 1
i:         % Input n and push [1 2 ... n]
"          % For each (that is, do the following n times)
%   Do...while
_Yq    %     Next prime
tq     %     Duplicate, subtract 1
G      %     Push n again
\      %     Modulo
%   End (implicit). Exit loop if top of stack is 0; else next iteration
% End (implicit)
% Display (implicit)


Perl, 77 76 + 1 = 77 bytes

for($p=2;@a<$_;$p++){push@a,$p if(1 x$p)!~/^(11+?)\1+$/&&($p%$_<2)}say$a[-1]  Uses the prime-testing regex to determine if $p is prime, and makes sure that it's congruent to 1 mod the input (the only nonnegative integers below 2 are 0 and 1, but it can't be 0 if it's prime, so it has to be 1. saves 1 byte over ==1).

• This appears to print 3 for input 1 (should be 2). Commented Nov 17, 2016 at 4:13
• You can save 10 byte by doing (1 x++$.)!~/^(11+?)\1+$/&&($.%$_<2)&&push@a,$.while@a<$_;say$a[-1] (it's what I was talking about in my previous comment). However the output (of either version) seems wrong for at least 2 and 3... – Dada Commented Nov 17, 2016 at 18:16 Mathematica 44 Bytes  Pick[x=Table[i #+1,{i,# #}],PrimeQ/@x][[#]]&  Very fast. Uses the idea from the "Note" % /@ {1, 2, 3, 4, 100, 123} // Timing  Output {0.0156001, {2, 5, 19, 29, 39301, 102337}}  Perl 6, 46 39 37 bytes ->\n{(2..*).grep({.is-prime&&($_-1)%%n})[n-1]}

->\n{(1,n+1...*).grep(*.is-prime)[n-1]}

{(1,$_+1...*).grep(*.is-prime)[$_-1]}


Java 8, 84 bytes

Golfed

(n)->{for(int s=n,i=1;;i+=n)for(int j=2;i%j>0&j<i;)if(++j==i&&--s<1)return n>1?i:2;}


Ungolfed

(n) -> {
for (int s = n,      // Counting down to find our nth prime.
i = 1;           // Counting up for each multiple of n, plus 1.
;                // No end condition specified for outer for loop.
i += n)          // Add n to i every iteration.
for (int j = 2;      // Inner for loop for naive primality check.
i % j > 0)      // Keep looping while i is not divisible by j
// (and implicitly while j is less than i).
if(++j==i       // Increment j. If j has reached i, we've found a prime
&&              // Short-circutting logical AND, so that we only decrement s if a prime is found
--s < 1)        // If we've found our nth prime...
return n>1?i:2; // Return it. Or 2 if n=1, because otherwise it returns 3.
}


Explanation

Solution inspired by several other answers. Function is a lambda that expects a single int.

The n>1?i:2 is a cheap hack because I couldn't figure out a better way to consider the case of n=1.

Also, this solution times out on Ideone, but has been tested for all test cases. It times out because in order to shave a couple bytes off, I took out the explicit j<i check in the inner loop. It's mostly implied by i%j>0... except in the case of i=1 and j=2 (the very first iteration), in which case the loop runs until j overflows (I'm assuming). Then it works fine for all iterations afterwards.

For a version that doesn't time out that's a couple bytes longer, see here!

Racket 109 bytes

(let p((j 2)(k 0))(cond[(= 0(modulo(- j 1)n))(if(= k(- n 1))j(p(next-prime j)(+ 1 k)))][(p(next-prime j)k)]))


Ungolfed:

(define (f n)
(let loop ((j 2)
(k 0))
(cond
[(= 0 (modulo (sub1 j) n))
(if (= k (sub1 n))
j
[else (loop (next-prime j) k)]  )))


Testing:

(f 1)
(f 2)
(f 3)
(f 4)
(f 100)
(f 123)


Output:

2
5
19
29
39301
102337


Ruby 64 bytes

require'prime';f=->(n){t=n;Prime.find{|x|(x-1)%n==0&&(t-=1)==0}}


Called like this:

f.call(100)
# 39301


Also, this command-line app works:

n=t=ARGV[0].to_i;p Prime.find{|x|(x-1)%n==0&&(t-=1)==0}


called like this

ruby -rprime find_golf_prime.rb 100


but I am not so sure how to count the characters. I think I can ignore the language name, but have to include the -rprime and space before the script name, so that is slightly shorter, at 63 . . .

R, 72 bytes

n=scan();q=j=0;while(q<n){j=j+1;q=q+1*(numbers::isPrime(j)&!(j-1)%%n)};j


Terribly inefficient and slow but it works. It reads input from stdin and then uses the isPrime function from the numbers package to find the primes. The rest is just checking whether prime - 1 is divisible by n.

JavaScript (ES6), 65 bytes

f=(n,i=n,j=1)=>i?f(n,i-!/^(..+?)\1+\$/.test('.'.repeat(j+=n)),j):j


Uses the regexp primality tester, since it's a) 8 bytes shorter and b) less recursive than my pure recursive approach.

Axiom 64 bytes

f(n)==(n<0 or n>150=>0;[i*n+1 for i in 0..2000|prime?(i*n+1)].n)


does someone know how to write above using Axiom streams?... some example

-> f(i)  for i in 1..150
Compiling function f with type PositiveInteger -> NonNegativeInteger

[2, 5, 19, 29, 71, 43, 211, 193, 271, 191, 661, 277, 937, 463, 691, 769,
1531, 613, 2357, 1021, 1723, 1409, 3313, 1609, 3701, 2029, 3187, 2437,
6961, 1741, 7193, 3617, 4951, 3877, 7001, 3169, 10657, 6271, 7879, 5521,
13613, 3823, 15137, 7349, 9091, 7499, 18049, 6529, 18229, 7151, 13159,
10141, 26501, 7669, 19801, 11593, 18127, 13109, 32569, 8221, 34649, 17981,
21799, 16001, 28081, 10429, 39799, 19381, 29947, 14771, 47713, 16417,
51539, 25013, 29101, 26449, 50051, 16927, 54037, 23761, 41149, 31489,
68891, 19237, 51341, 33713, 45589, 34057, 84551, 19531, 64793, 42689,
54499, 41737, 76001, 27457, 97583, 40867, 66529, 39301, 110899, 29989,
116803, 49297, 51871, 56711, 126047, 38557, 133853, 42901, 76369, 53089,
142607, 40129, 109481, 63337, 83071, 67733, 112337, 41281, 152219, 70639,
102337, 75641, 126001, 42589, 176531, 85121, 107071, 62791, 187069, 55837,
152419, 94873, 104761, 92753, 203857, 62929, 226571, 72661, 144103, 99401,
193051, 69697, 168781, 112859, 133183, 111149, 250619, 60601]


Husk, 9 8 bytes

!⁰fṗ¡+⁰1


Try it online!

!⁰         # get the input-th element of
fṗ       # the elements that are primes among
¡      # the list formed by repeatedly
+⁰    # adding the input to the last result
1   # starting with 1.