# Smallest positive integer not yet appeared so that the sum of the first n elements is divisible by n

Given positive integer n, output a(n) where a is the sequence defined below:

a(n) is the smallest positive integer not yet appeared so that the sum of the first n elements in the sequence is divisible by n.

# Example

• a(1) is 1 because it is the smallest positive integer that has not appeared in the sequence, and 1 is divisible by 1.
• a(10) is 16 because look at the first nine elements: 1,3,2,6,8,4,11,5,14. They sum up to 54, so for the first ten elements to sum up to a multiple of 10, a(10) would need to have a remainder of 6 when divided by 10. 6 has already appeared, so a(10) is 16 instead.

# Testcases

n     a(n)
1     1
2     3
3     2
4     6
5     8
6     4
7     11
8     5
9     14
10    16
11    7
12    19
13    21
14    9
15    24
16    10
17    27
18    29
19    12
20    32
100   62
1000  1618
10000 16180


# References

• What values of n and a(n) must we support? – Rohan Jhunjhunwala Aug 18 '16 at 1:42
• @RohanJhunjhunwala Theoretically every positive number. – Leaky Nun Aug 18 '16 at 1:44
• so bignum mandatory? – Rohan Jhunjhunwala Aug 18 '16 at 1:47
• @RohanJhunjhunwala I said theoretically, meaning it is not mandatory. – Leaky Nun Aug 18 '16 at 1:47
• so less than 2^31 -1 is ok? – Rohan Jhunjhunwala Aug 18 '16 at 1:49

## Python 2, 43 bytes

r=.5+5**.5/2
lambda n:[n/r+1,n*r][n%r<1]//1


Outputs floats. Uses the relation

a(n) = A002251(n-1) + 1

to Wythoff pairs. Takes from the upper or lower Beatty sequence by multiplying or dividing by the golden ratio and converting to an integer.

• I think the precision is fine up to 2**32. – xnor Aug 18 '16 at 4:27
• Then it does not work outside the boundary. – Leaky Nun Aug 18 '16 at 4:28
• @LeakyNun I thought you said up to 2^31 -1 is ok? – xnor Aug 18 '16 at 4:30
• What does it return for 2^31-1? – Leaky Nun Aug 18 '16 at 4:34
• @LeakyNun It gives 6949403065.0. – xnor Aug 18 '16 at 13:35

# OCaml, 163 bytes

open List
let a x=let rec h m s=let rec n m s c=if fold_left(+)c(s)mod m<>0||mem c s then n m s(c+1)else c in if m=x then hd s else h(m+1)((n(m+1)s 2)::s) in h 1


Online interpreter

### Usage

>> open List
>> let a x=let rec h m s=let rec n m s c=if fold_left(+)c(s)mod m<>0||mem c s then n m s(c+1)else c in if m=x then hd s else h(m+1)((n(m+1)s 2)::s)in h 1;;
<< val a : int -> int = <fun>
>> a(100);;
<< int = 62


where >> is STDIN and << is STDOUT.

• Can you remove the whitespace after the last in? – Leaky Nun Aug 18 '16 at 6:28
• I'm guessing you meant before? Thanks for editing in the demo! – m-chrzan Aug 18 '16 at 6:38
• Yes, I meant before – Leaky Nun Aug 18 '16 at 6:39

# Python 3, 102 bytes

Definitely not the shortest solution (not familiar with code golf) but I was bored so here it is in Python. I'm sure you could make it smaller with lambdas/filter.

def a(n,s=[]):
for j in range(1,n+1):
i=1
while i in s or(sum(s)+i)%j:i+=1
s+=[i]
return s[-1]

• Use a while loop for the second nested loop. Your solution currently does not theoretically support higher integers. – Leaky Nun Aug 18 '16 at 2:38
• Rather than using 4 spaces, you can use a tab or one space. – Leaky Nun Aug 18 '16 at 2:48
• You can also use space for the first level and then tab for the second level. – Leaky Nun Aug 18 '16 at 2:48
• Make sure to include your byte count. – Leaky Nun Aug 18 '16 at 2:48
• You ca put the opposite of the if condition as the while condition, and then append the item to the array outside the while loop. – Leaky Nun Aug 18 '16 at 3:01

# Pyth - 2321 18 bytes

Can probably streamline the generation process with more lambdas or other tricks, but this is my first answer in more than a month.

eem=+Yf!|}TY%+TsYh


# R, 99 bytes

f=function(n){a=n
b=c()
while(0<(a=a-1))b=c(f(a),b)
while(a<-a+1)if(!(sum(b)+a)%%n&!a%in%b)break
a}


Simple algorithm. Runs from n-1 to 1 and gathers all of those numbers in the sequence. Then it moves up from 1 -- checking membership and whether it divides appropriately.

# Actually, 17 bytes

This uses xnor's algorithm. Golfing suggestions welcome. Try it online!

,;;φ(/u(φ*1φ(%<I≈


Here's a 31-byte version that uses the function definition, but with the oddity that, at first, the function returns the sequence a(n)-1, so the result needs to be incremented at the end. Try it online!

[]╗,1";#╜+;l@Σ%@╜í+uY"£╓╖n╜Nu


Ungolfing:

First algorithm

,;;                 Take the input, duplicate it twice
1φ(%<I    If input mod phi less than 1
(φ*          then input * phi
φ(/u             else input / phi + 1
≈   int() the result

Second algorithm

[]╗    Push a list to register 0 (call this res from now on)
,      Take input
1     Start function, push 1
"      Start string
;      Duplicate i
#╜+;   res + list(i), duplicate
l      len(new list)
@Σ     sum(new list)
%      sum % len
@╜í    Rotate i to top, check if i in res
+uY    (sum%len) + (i in res) + 1, negate (1 if i fits conditions, else 0)
"£     End string, turn into a function
╓      Push first (1) values where f(x) is truthy, starting with f(0)
╖     Append result to the list in register 0, end function
n      Run function (input) times
╜Nu    Return res[-1]+1


# Python 3, 96 bytes

n=int(input())
a=[]
for L in range(1,n+1):
t=L-sum(a)%L
while t in a:t+=L
a+=[t]
print(a[-1])


Ideone it!

## JavaScript (ES6), 69 bytes

n=>{for(a=[],s=i=0;i++<n;a[j]=1,s+=j)for(j=i-s%i;a[j];)j+=i;return j}


At each stage just checks all the numbers with the appropriate remainder until it finds one that it hasn't seen before, then marks it seen and updates the total.