6
\$\begingroup\$

In this challenge we'll compute an infinite minimal admissible sequence.

The sequence for this challenge starts with a(1) = 1.

We continue this sequence by finding a(n) as the smallest possible number such that a(n) > a(n-1) and for every prime p, the set {a(i) mod p : 1 ≤ i ≤ n} has at most p-1 elements.

Write a program or function that takes positive integer n and outputs a(n). Shortest code in bytes wins.


Example:

a(6) is 19, rather than, say 17 because [1,3,7,9,13,19] (the previous terms) is admissible while [1,3,7,9,13,17] is not.

[1,3,7,9,13,17] is not admissible, because for the base 3, after taking the modulo of each term with 3, we obtain [1,0,1,0,1,2] which contains every non-negative number smaller than 3, our chosen base.

For [1,3,7,9,13,19] however, it would be impossible to come up with a base such that the list after modulo contains every non-negative integer smaller than such base.


Reference:


Testcases:

a(1) = 1
a(2) = 3
a(3) = 7
a(4) = 9
a(5) = 13
a(6) = 19
a(7) = 21
a(8) = 27
a(9) = 31
a(10) = 33
a(100) = 583
\$\endgroup\$
  • \$\begingroup\$ Can we use 0-based index? \$\endgroup\$ – Leaky Nun Aug 14 '16 at 12:13
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Aug 14 '16 at 13:19
  • \$\begingroup\$ @LeakyNun For this one, sure. \$\endgroup\$ – orlp Aug 14 '16 at 15:32
1
\$\begingroup\$

Brachylog, 44 bytes

-:[1]r:[1]cit.
t<gX=:?rc.'(l:2eLg:.rz:%adlL)

Try it online!

100 takes about a minute here, so be patient if you want to try 100.

Predicate 0 (main predicate)

-:[1]r:[1]cit.
-:[1]r:[1]c     create array [[1], input-1, 1]
           i    iterate: [1] as input, iterate (input-1) times, predicate 1
            t.  last element is the output

Predicate 1 (auxiliary predicate)

t<gX=:?rc.'(l:2eLg:.rz:%adlL)
t<                              last element of input < Temp
  gX                            [Temp] = X
   X=                           Assign a value to X, which assigns
                                a value to Temp
   X :?rc.                      [Input,X] concatenated is output
         .'(                )   The following about the output cannot
                                be proven:
            l:2eL                   L is a number between 2 and length
                                    of output, inclusive
                Lg:.rz:%a           every element of output, taken modulo L,
                         dlL        after removing duplicates, has length L
\$\endgroup\$
1
\$\begingroup\$

ES6, 91 bytes

(n,a=[i=1])=>a[n]||f(n,a.every((_,j)=>(j+=2)>new Set(b.map(e=>e%j)).size,b=[...a,+++])?b:a)

Zero-indexed. Due to its recursive nature, only works for the first 450 terms, but computes a(99)=583 almost instantly.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.