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

Question

Task

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

• a(n) from n=1 to n=10000

References

• OEIS A019444

Answer 1

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.

Answer 2

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[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[1];;
<< val a : int -> int = <fun>
>> a(100);;
<< int = 62

where >> is STDIN and << is STDOUT.

Answer 3

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]

Answer 4

Pyth - 23 21 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

Try it online here.

Answer 5

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

Answer 6

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.

Answer 7

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!

Answer 8

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.

Answer 9

Behaviour, 64 bytes

c=&[(~!a{})(l=c:a-1s=0\(~(l<=s+=1)~!(l+s>&a+b)%a)l+s)]f=&(!c)%-1

Test with:

f:1
f:2
f:10

Calculates the list recursively and doesn't even work for n > 300, but you know, there was an attempt.

Ungolfed and commented:

// There are two functions, the first is recursive and creates the entire list
createList = &
  [
    (~!a; {})    // Base case, n==0 return empty list
    (
      list = createList:a-1 // create the list for n-1
      smallest = 0          // initialize the variable to find the smallest
                            // Repeat the following Sequencer until success
      \(
        // Increments smallest and check if it is NOT on the list
        ~(list <= smallest+=1) 
        
        // sum up the list with the smallest found
        sum = list+smallest > &a+b
        
        // is the sum divided by n remainder 0
        ~!sum%a 
      )
      // returns the list with the smallest
      list + smallest
    )
  ]
// The second function just execute the first and return its last item
f = &(!createList)%-1