# A083569: Smallest m not occurring earlier such that m+n is prime

Define a 1-indexed sequence as follows:

• A083569(1) = 1
• A083569(n) where n is an integer greater than 1, is the smallest integer m not occurring earlier such that m+n is a prime number.

Your task is to take in n and return A083569(n).

 n  A083569(n)
1  1
2  3
3  2
4  7
5  6
6  5
7  4
8  9
9  8
10 13
11 12
12 11
13 10
14 15
15 14
16 21
17 20
18 19
19 18
20 17


More testcases can be found here. The original sequence on OEIS can be found here.

This is . Shortest answer in bytes wins. Standard loopholes apply.

• @Mr.Xcoder "Define a 1-indexed sequence as follows" – Leaky Nun Jun 19 '17 at 9:45

Thanks to xnor for suggesting some changes that saved 3 bytes!

f n=[m|m<-[1..],all((>0).mod(n+m))[2..n+m-1],all((/=m).f)[1..n-1]]!!0


Try it online!

## Explanation

We define a function f n. We define f n to be the first element !!0 of the list:

[m|m<-[1..],all((>0).mod(n+m))[2..n+m-1],all((/=m).f)[1..n-1]]


Broken down that is:

[m|          # Numbers m
m<-[1..],    # From the integers greater than 0
all          # Forall x
(>0).mod(n+m)# n+m mod x is not zero
[2..n+m-1]   # from the integers from 2 to n+m-1
all          # Forall
((/=m).f)    # when f is applied the result is not m
[1..n-1]     # from the integers from 1 to n-1

• Welcome to Haskell golfing! The[2,3..] can just be [2..], counting up by 1 is default. There's a built-in notElem. – xnor Jun 19 '17 at 4:20
• @xnor Thanks! I ended up finding a better way around using notElem but the first tip was helpful and I'll make sure to keep that second one in my back pocket. – Wheat Wizard Jun 19 '17 at 4:32
• Looks like your new revision gets f 1 wrong, should be 1. – xnor Jun 20 '17 at 5:06
• @xnor Fixed, unfortunately at the cost of 3 bytes. – Wheat Wizard Jun 20 '17 at 5:20

# Jelly, 16 15 bytes

Rɓ²R+⁸ÆPTḟḢṭµ/Ṫ


This assumes A083569(n) ≤ n² (the sequence appears to be growing linearly).

Try it online!

### How it works

Rɓ²R+⁸ÆPTḟḢṭµ/Ṫ  Main link. Argument: n

R                Range; yield [1, ..., n].
ɓ               Begin a dyadic chain with swapped arguments.
µ/   Reduce the range by that chain.
If we call the chain f, this computes f(2,1), then f(3,f(2,1)),
then f(4,f(3,f(2,1)), etc.
The left argument is an integer k, the right one an array A.
²                Square; yield k².
R               Range; yield [1, ..., k²].
+⁸             Add k, yielding [1+k, ..., k²+k].
ÆP           Test each sum for primality.
T          Truth; get all indices of 1‘s. This finds all m in [1, ..., k²]
such that m+k is prime.
ḟ         Filterfalse; remove all resulting elements that appear in A.
Ḣ        Head; extract the first remaining result.
ṭ       Tack; append the extracted integer to A.
This computes the first n elements of the sequence.
Ṫ  Tail; extract the last, n-th element.

• Indeed, A083569(n) is at most the nth prime larger than n by its definition, which is at most the 2nth prime, which (for n≥3) is less than 4n*log(n) by results of Rosser–Schoenfeld. – Greg Martin Jun 19 '17 at 5:28
• While @GregMartin verified it, it's still a pretty wild assumption to make... – Esolanging Fruit Jun 19 '17 at 6:18
• @Challenger5 I prefer "educated guess". – Dennis Jun 19 '17 at 6:25

# Pyth - 1817 15 bytes

Thanks to @isaacg for saving me two bytes!

Back on this site, after being busy for a while, will hopefully golf this one further.

esmaYf&-TYP_+Th

• Welcome back to PPCG! – Leaky Nun Jun 19 '17 at 3:53
• @LeakyNun Thanks :) – Maltysen Jun 19 '17 at 3:58
• -TY is one byte shorter than !/YT, and truthy in the same cases. – isaacg Jun 19 '17 at 8:04
• You can save another byte by changing +hdT to +Th. – isaacg Jun 19 '17 at 8:08
• @isaacg, oh does it cast the first element to a list? That's really cool. – Maltysen Jun 19 '17 at 11:27

# C# (.NET Core), 169 bytes

n=>{if(n<2)return 1;var p=new int[n-1];int i=0,j,s;for(;i<n-1;)p[i]=f(++i);for(i=1;;i++){for(j=2,s=i+n;j<s&&s%j++>0;);if(j==s&!System.Array.Exists(p,e=>e==i))return i;}}


Try it online!

By far the most inefficient way to calculate the results, so please refrain from calculating f(n) for n>=30 with this code. The first step is to recursively calculate the values from f(1) to f(n-1) and then proceed to calculate f(n) by searching for the first i such that n+i is prime and i is not in the previous values list.

# x86-64 Assembly, 57 55 bytes

I'm new to golfing, so comments/feedback are appreciated.

Note: this is optimized for machine code length, not for source length.

0: 89 f8 ff cf 74 32 97 89 fe 89 f1 ff c6 89 f0 99
1: f7 f1 85 d2 e0 f7 85 c9 75 ed 89 f9 ff c9 56 29
2: fe 56 57 51 89 fc e8 d3 ff ff ff 59 5f 5e 39 c6
3: e0 ef 96 5e 74 d1 c3


Defines a function, using the standard convention (i.e. return value in eax, first argument in edi, all registers caller-saved except ebx) that takes an unsigned 32-bit integer and returns the smallest m etc.

Source:

    .globl a083569
// edi = original, probably don't touch
// esi = candidate prime, if it's not a repeat we return edi-this
a083569:
mov %edi, %eax
dec %edi
jz end
xchg %eax, %edi
mov %edi, %esi
primecheck:
mov %esi, %ecx
inc %esi
primeloop:
mov %esi, %eax
cdq
div %ecx
test %edx, %edx
loopnz primeloop
/* end */
// if esi isn't prime, then ecx is now one or greater.
test %ecx, %ecx
jnz primecheck
// esi is now our target prime: check if it's not already one
mov %edi, %ecx
dec %ecx
push %rsi   /* we need a flag-safe way to restore this later */
sub %edi, %esi
chkdup:
push %rsi
push %rdi
push %rcx
mov %ecx, %edi
call a083569
pop %rcx
pop %rdi
pop %rsi
cmp %eax, %esi
loopne chkdup
/* end loop - chkdup */
xchg %esi, %eax
pop %rsi
je primecheck
/* end outer loop - primecheck */
end:
ret


Try it online!

## Clojure, 158 155 bytes

#(loop[r[0 1]i 1](if(= i %)(last r)(recur(conj r(nth(for[j(range):when(=((set r)j)(seq(for[k(range 2(+ 1 i j)):when(=(mod(+ 1 i j)k)0)]j)))]j)0))(inc i))))


This might still have some fat, I'm not quite happy with (+ 1 i j) but this was the easiest way to handle base case n = 1 and the rest. ((set r)j) returns nil if j is not in the set, and (seq ()) on an empty list returns nil as well. Calculates n = 1000 in 48 seconds.

Update: removed nil from = check as the code works correctly also without it.

# Ruby, 62+8 = 70 bytes

Uses the -rprime flag.

f=->n,o=[]{o<<f[n-1,o]if n>1;Prime.find{|i|i>n&&o|[i-n]!=o}-n}


Try it online!

# Python, 194170 110 bytes

84 bytes saved by Leaky Nun

2 bytes saved by mathmandan

def s(n):
a=[s(j)for j in range(1,n)];i=1
while(i in a)|any((i+n)%j<1for j in range(2,i+n)):i+=1
return i


Defines a function s(n) that takes a number as input and returns A083569(n).

Try it Online

• You might consider including this TIO link. – Leaky Nun Jun 19 '17 at 3:55
• You can use p=lambda n:any(n%i<1for i in range(2,n)) for the primality check. – Leaky Nun Jun 19 '17 at 4:06
• 110 bytes – Leaky Nun Jun 19 '17 at 7:09
• You can use bitwise or to save a couple bytes: while(i in a)|any(... – mathmandan Jun 19 '17 at 16:38

# Husk, 16 bytes

!¡λḟȯṗ+→L¹-N);1
`

Try it online!

1-indexed.