Seqindignot sequence

Question

Title is made up, from 'Sequence Index Digit Not'.

Challenge:

Given an integer n which is >= 0, output the n'th number of the following sequence.
Here are the first 50 items, with it's (0-indexed) index above it:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
1 0 3 2 5 4 7 6 9 8 22 20 30 24 23 26 25 28 27 32 11 33 10 14 13 16 15 18 17 31 12 29 19 21 50 40 41 42 44 45 35 36 37 51 38 39 52 53 55 56 34

How does this sequence work?

The number at index n must be the first in order that does not have any digits in common with n, and hasn't occurred yet for previous indexes. So when we look at normal sequence like this from 0-60:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

We define the n'th values like this:

• 0: The first number (0) contains the same digit, so we look for the next (1), which does not contain the same digit. So n=0 outputs 1.
• 1: The first number (0) does not contain the same digit, so n=1 outputs 0.
• 2: We've already encountered 0 and 1, and the next digit (2) contains the same digit, so we look for the next (3), which does not contain the same digit. So n=2 outputs 3.
• ...
• 10: We've already encountered 0-9, so the next in line is 10. 10-19 contain the matching digit 1, 20 contains the matching digit 0, 21 contains the matching digit 1 again, 22 is valid, so n=10 outputs 22.
• etc.

Challenge rules:

• If your language is 1-indexed (or you choose to) you are allowed to start the sequence at 3 2 5 4 7 ... (skipping the 1 at n=0 and the 0 at n=1).
• The minimum largest index you should support is 25,000. NOTE: The sequence stops at index 1,023,456,788, because the next index in line contains all 10 digits.
• You are also allowed to output / return an array/list of the entire sequence up to and including index n if you want to.

General rules:

• This is code-golf, so shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code.
• Also, please add an explanation if necessary.

Test cases:

This sequence actually created pairs regarding index and outputs. If index n outputs o, index o outputs n. So you can input either the left or right, and the output will be the other side:

0      <->  1       (this test case is optional)
2      <->  3
10     <->  22
12     <->  30
34     <->  50
89     <->  100
111    <->  200
112    <->  300
199    <->  322
2231   <->  4456
9605   <->  11118
19235  <->  46000
23451  <->  60668
25000  <->  13674

Here is a pastebin of the first 25,001 test cases if you want to try others.

Answer 1

Pyth, 18 bytes

u+Gf!|}TG@`H`T0hQY

Try it here! or Check more test cases!

Note that this returns the entire sequence up to index N, but the link returns the last number only, by prepending an e (end). If you want to see the raw value returned by this program, just remove it.

How it works

u+Gf!|}TG@`H`T0hQY  - Full program.

u     ...      hQY  - Reduce hQ (the input incremented) from left to right, with the
                       function ...(G, H), with starting value Y (the empty list).
                       G is the current value and H is the iteration index.
   f          0     - First integer starting from 0, that satisfies the following:
      }TG             - Appears in G...
     |   @`H`T        - Or its (string) intersection with the current index (H) is
                        non-empty.
    !                 - Logical NOT (boolean negation).
 +G                 - Append the value obtained above to the current value (G).
                      This becomes the given value for the next iteration.
                    - Implicitly print all intermediate results, or add e to print 
                      the last one.

Answer 2

Python 2, 92 91 89 88 bytes

a=()
i=0
exec"x=0\nwhile set(`x`)&set(`i`)or x in a:x+=1\na+=x,;i+=1;"*-~input()
print a

Try it online!

Prints a list of the first n+1 numbers

---

Different approach, which is a lot faster:

Python 2, 96 bytes

n=input()
r=range(9*n)
i=0
exec"x=0\nwhile set(`r[x]`)&set(`i`):x+=1\nprint r.pop(x),;i+=1;"*-~n

Try it online!

Answer 3

Haskell, 80 69 bytes

f n=[x|x<-[0..],all(`notElem`show n)$show x,all(/=x)$f<$>[0..n-1]]!!0

Try it online!

Very slow for large n.

f n=
    [x|x<-[0..]     ] !!0          -- pick the first of all 'x' from [0..]
                                   -- where
      all(`notElem`show n)$show x  -- no digit of 'n' appears in 'x', and
      all(/=x)                     -- 'x' is not seen before, i.e. not in the list
               f<$>[0..n-1]        -- 'f' mapped to [0..n-1]

Edit: @Laikoni saved 10 bytes. Thanks!

Answer 4

Java (OpenJDK 8), 218 217 213 210 202 200 172 171 170 168 167 bytes

I cannot believe that I didn't just return k all this time...

i->{int j=-1,k=0,y=1;for(String r=" ",e=r;j++<i;r+=~-k+e,y=1)for(k=0;y>0;k++)for(int f:(k+(y=0)+"").getBytes())y+=(e+j).indexOf(f)<0&!r.contains(e+k+e)?0:1;return~-k;}

Try it online!

Answer 5

APL (Dyalog), 39 bytes

0∘{0=⍵:1⋄(~⍺∊0∇¨⍳⍵)∧⊃∧/≠/⍕¨⍺⍵:⍺⋄⍵∇⍨⍺+1}

Uses ⎕IO←0.

Try it online!

How?

Recursion.

0=⍵:1 - take a guess.

~⍺∊0∇¨⍳⍵ - left arg (accumulator) is not already in previous results

∧⊃∧/≠/⍕¨⍺⍵ - and the string representation of the accumulator and n are different

:⍺ - then return the accumulator.

⍵∇⍨⍺+1 - otherwise, increment accumulator and recurse.

Answer 6

Python 3, 92 bytes

o=1,
for i in range(int(input())):
 x=0
 while{*str(x),x}&{*str(~i),*o}:x+=1
 o+=x,
print(o)

Try it online!

This prints all the terms up to the Nth one. Thanks to Dennis for  -4  -5 bytes!

Answer 7

JavaScript (ES6), 103 88 81

Edit Revised including many clever ideas by @Neil

n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

Starting point

Basic idea: a loop from 0 to n, and an inner loop checking values still not used

n=>{
  var r=[]
  for(i=0;i<=n;i++)
  {
    s=new Set(i+'')
    for(j=-1;s;)
    {
      if (!r[++j] && ![...j+''].some(d=>s.has(d)))
      {
        r[j]=1
        console.log(i,j)
        s=0
      }
    }
  }
  return j
}

Current version more readable

n=>{
  for(r = [j=i=0]; i <= n; )
    if (r[j] || (i+'').match(`[${j}]`))
      ++j
    else
      r [k=j] = ++i,
      j = 0;
  return k
}

Test

var f=
n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

update=_=>{
  var i=+I.value
  if (i < 1e4 || confirm("Really?")) {
    O.textContent=i + ' -> ...'
    setTimeout(_=>O.textContent=i + ' -> ' + f(i), 100)
  }
}  

update()

<input id=I value=100 type=number max=1023456788>
<button onclick='update()'>Go</button>
(slow when input > 1000)
<pre id=O></pre>

Answer 8

Go, 217 205 bytes

package g;import("fmt";"strconv";"strings");var(
d=make(map[int]int)
a=strconv.Itoa)
func G(L int){k,i:=0,0;for;i<=L;i++{s:=a(i);k=0;for d[k]>0||strings.ContainsAny(a(k),s){k++;}
d[k]=1;}
fmt.Print(a(k));}

Alternate version (program instead of a package): Try it online!

Improvements:

• removed space after outer for by using multiple assignment for i,k
• importing "fmt"; + fmt.Print is shorter than os.Stdout.WriteString (holdover from package main when os.Args was needed)

Answer 9

Octave, 114 bytes

N=input("");o=[1];for i=1:N;j=0;while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));j++;end;o=[o,j];end;[0:N;o]

Try it online!

Thanks to Kevin Cruijssen and Dlosc for the character comparison golfing.

Ungolfed

N=input("");o=[1];

for i=1:N;
    j=0;
    while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));
        j++;
    end;
    o=[o,j];
end;
[0:N;o]

Basic explanation:

• Outer loop and inner loop, one for index i, and another for value to add j

• For each i, continue to increment j if either of the following are met:

  1. Any j has been used before
  2. This one gets fun. First, split each numeric value into a vector of digits (e.g., 10 becomes [1 0]) using int2str. Then, compare the two numbers using ismember(e.g., [1 0] and [2 1] would return [1 0]) and then nnz to see if any columns matched.

• If none of the above are met, you have the next number! Append to o, the output matrix

• Print original indices with output matrix

Answer 10

Perl 5, 60 bytes

59 bytes code + 1 for -p.

$_="@{[0..($;=++$_)*9]}";$_=eval's/\b[^ $-]+ //;$-++;$&;'x$

Try it online! (Includes -l for visual purposes and $-=0; to reset each iteration)

Answer 11

Pip, 30 bytes

29 bytes of code, +1 for -p flag.

Fn,a+1{Y0WyNl|_NyMSn++ylPBy}l

Try it online!

Outputs the whole list. Warning: highly inefficient; the 2231 input case has been running for 35+ minutes on my laptop and still hasn't finished.

Explanation

                               a is cmdline arg, l is [] (implicit)
Fn,a+1{                    }   For each n in range(a+1):
       Y0                       Yank 0 into y
         W                      While...
          yNl|                  y is in l, or...
              _Ny               lambda function: arg is in y
                 MSn            mapped to digits of n and result list summed
                                (i.e., any digit of n is in y):
                    ++y          Increment y
                       lPBy     Once we have a y that meets the criteria, push it to
                                the back of l
                            l  Output l (formatted with -p flag)

Answer 12

Visual Basic .NET (.NET 4.5), 260 259 bytes

-1 byte thanks to Kevin Cruijssen

Function A(n)
Dim p=New System.Collections.Generic.List(Of Long),j="0",g=0
For i=0To n
j=0
While 1
If Not p.Contains(j)Then
g=1
For Each c In i.ToString
If j.Contains(c)Then g=0
Next
If g Then Exit While
End If
j+=1
End While
p.Add(j)
Next
A=p(n)
End Function

Loops through, generating previous terms in the sequence to then compare later. Then iterates the number as a string looking for matches.

Abuses VB.NET's typing system. For example, j is a string, but adding one converts to an integer for me. Integers are converted to Booleans where 0 is False and the rest are True.

Try it online!

Answer 13

Jelly, 20 bytes

^{Pyth beats Jelly. Go Mr. Xcoder!}

Df⁹LD¤ȯeṆ
0ç1#ɓ;
1Ç¡

A full program taking input from STDIN and outputting in the list format option using Jelly's list representation*. Uses the standard 0 based indexing.

* single element lists have no surrounding [], so 0 outputs 1, while 1 outputs [1, 0] etc.

Try it online!

How?

Df⁹LD¤ȯeṆ - Link 1, can append n to current? n, number; current, list
D         - convert n to decimal list
     ¤    - nilad followed by link(s) as a nilad:
  ⁹       -   chain's right argument, current
   L      -   length
    D     -   convert to a decimal list
 f        - filter discard from left if not in right
       e  - n exists in current?
      ȯ   - left logical OR right (empty lists are falsey)
        Ṇ - logical NOT

0ç1#ɓ; - Link 2, append next number: current, List
   #   - n find (count up finding first n matches):
  1    - ...finding: 1 match
0      - ...stating at: n=0
 ç     - ...doing: the last link as a dyad (left=n, right=current)
    ɓ  - new swapped-arg-dyadic chain (left = current, right = list of the found n)
     ; - concatenate

1Ç¡ - Main link: no arguments
1   - initialise the return value to 1
  ¡ - repeat input() times:
 Ç  -   last link (2) as a monad
    - implicit print