27
\$\begingroup\$

Challenge

Here at PPCG, we sure do like our sequences, so here's a fun another one.

Let's define a(n) as being the smallest non-negative integer X that is not equal to any a(k) (0 < k < n), and a(n-1) and X do not share any decimal digits. a(0) = 0

Given an input n > 0, output such a(n).

For example, for input n = 13, we have a(13) = 20, since a(12) = 11 and 20 is the smallest non-negative integer we haven't seen yet that doesn't share any decimal digits with 11.

Sequence

Here are the first 20 terms to get you started. This is sequence A067581 on OEIS.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 11, 20, 13, 24, 15, 23, 14, 25

Rules

  • The input and output can be assumed to fit in your language's native integer type.
  • The input and output can be given in any convenient format.
  • You can choose to either 0-index, as I am here in my examples, or 1-index for your submission. Please state which you're doing.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so other people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
3
  • \$\begingroup\$ Can we get n > 1 (or n ≥ 2) as input? (1-indexing) \$\endgroup\$ Aug 10, 2017 at 15:20
  • \$\begingroup\$ @EriktheOutgolfer Sure, that's fine. I apparently missed that bullet point when copy-pasting, because that's a standard of my challenges. \$\endgroup\$ Aug 10, 2017 at 15:49
  • 5
    \$\begingroup\$ The scatter plot sure looks nice:) \$\endgroup\$
    – flawr
    Aug 10, 2017 at 18:40

8 Answers 8

10
\$\begingroup\$

Python 2, 85 bytes

-1 byte thanks to Dead Possum

n=0,
exec"i=0\nwhile set(`i`)&set(`n[-1]`)or i in n:i+=1\nn+=i,;"*input()
print n[-1]

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ n=0, for -1 byte? \$\endgroup\$ Aug 10, 2017 at 15:55
  • \$\begingroup\$ @DeadPossum yeah, thanks c: \$\endgroup\$
    – Rod
    Aug 10, 2017 at 15:57
7
\$\begingroup\$

Japt, 18 bytes

@A{!ZøA «As oX}a}g

Test it online! I've just added the g feature used here, but it's something I've been meaning to add for a long time (and this pushed me over the edge, because my non-g solution was around 35 bytes).

Explanation

@   A{!ZøA «  As oX}a}g
XYZ{A{!ZøA &&!As oX}a}gU
                           Implicit: U = input integer
   {                 }gU   Starting with [0, 1], return the U'th item generated by
XYZ{                 }     this function: (X = previous item, Y = index, Z = full array)
    A{             }a        Return the smallest non-negative integer A where
      !ZøA &&                  Z does not contain A (A is not yet in the sequence), and
             !As oX            A.toString() does not contain any of the same chars as X.
                           Implicit: output result of last expression
\$\endgroup\$
3
  • \$\begingroup\$ This makes my head hurt! But, then I've barely glanced at any of the function methods in Japt. \$\endgroup\$
    – Shaggy
    Aug 10, 2017 at 20:29
  • \$\begingroup\$ Isn't the default rule that you can't add something to the language after the question is given? It would be trivial otherwise to just always create a new built-in that solves the challenge, making them all arbitrarily short. \$\endgroup\$
    – trlkly
    Aug 11, 2017 at 13:02
  • \$\begingroup\$ @trlkly I believe it's allowed within good judgement. The built-in I added is much more general-purpose than just for this one answer. I think someone could theoretically add a built-in that solves the challenge entirely, but an answer like that would be sure to be received very poorly. \$\endgroup\$ Aug 11, 2017 at 13:53
5
\$\begingroup\$

Pyth, 20 bytes

eu+Gf!|/GT@`eG`T0Q]0

Try it online! or Try the test suite.

\$\endgroup\$
2
  • \$\begingroup\$ Mind if I add a test suite to your answer? \$\endgroup\$
    – Mr. Xcoder
    Aug 10, 2017 at 16:40
  • \$\begingroup\$ @Mr.Xcoder go ahead. \$\endgroup\$
    – Leaky Nun
    Aug 10, 2017 at 16:55
3
\$\begingroup\$

Haskell, 79 bytes

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

The code is horribly inefficient. To calculate bigger values, i.e. > 12, add f x|x<11=x between the two lines (implemented a g in the TIO link).

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 82 bytes

0-indexed.

f=(n,x=[1,p=0])=>n--?f(x[(g=k=>x[k]||(k+'').match(`[${p}]`)?g(k+1):p=k)(0)]=n,x):p

Demo

f=(n,x=[1,p=0])=>n--?f(x[(g=k=>x[k]||(k+'').match(`[${p}]`)?g(k+1):p=k)(0)]=n,x):p

for(n = 0; n < 50; n++) {
  console.log('a(' + n + ') = ' + f(n))
}

\$\endgroup\$
1
\$\begingroup\$

Husk, 18 bytes

!¡₁;0
ḟȯ¬V€d→⁰d-⁰N

A 1-indexed solution. Try it online!

Edit: fixed bug for +1 byte.

Explanation

Husk's built-in iteration function ¡ has many meanings. Here, I'm using "construct infinite list by repeatedly appending new elements computed from the existing ones". The second line is the helper function that computes a new element:

ḟȯ¬V€d→⁰d-⁰N  Takes a list of existing elements, e.g. x = [0,1,...,10]
           N  The positive integers
         -⁰   with elements of x removed:        [11,12,13,...
ḟȯ            Find an element n of this list that satisfies:
        d     Digits of n.
   V          Is any of them
    €         an element of
     d        the digits of
      →⁰      the last element of x?
  ¬           Negate.
              Returns 22.

The first line is the main function:

!¡₁;0  Takes an integer k.
 ¡     Iterate adding new elements to the list
   ;0  [0]
  ₁    using the helper function,
!      take k'th element of result.
\$\endgroup\$
1
1
\$\begingroup\$

Haskell, 78 bytes

n!k|r:_<-[j|j<-[1..],all(/=j)k,all(`notElem`show n)$show j]=n:r!(r:k)
(0![]!!)

It would be even more efficient if the second argument to ! would not be the list of seen numbers but of unseen numbers. But I can't do that without using more bytes.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Mathematica 115 Bytes

Still room to golf this down - and maybe use recursion (thus speeding it up).

(For[z={0};i=1,Length@z<#,
For[i=1,!FreeQ[z,i]||!DisjointQ@@IntegerDigits/@{l,i},i++];
z~AppendTo~i;l=Last@z;
];l)&

Original verbose code, with the same basic idea:

MakeSequenceA067581[n_]:=Module[{list={0}, innerCounter=1},

While[Length@list<n,
innerCounter=1;
(* inner loop *)While[Or[MemberQ[list,innerCounter],Intersection[IntegerDigits[Last@list],IntegerDigits[innerCounter]]!={}],innerCounter++];
AppendTo[list,innerCounter];
];
list
]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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