34
\$\begingroup\$

I absolutely hate the digit 1. So, I need your help to convert numbers to their "proper forms".

Numbers in proper form never have two 1s in a row. 101 is okay, but 110 is hideous.

To convert, simply skip all the improper numbers and count normally. For instance...

1 -> 1
2 -> 2
...
10 -> 10
11 -> 12
12 -> 13
...
108 -> 109
109 -> 120
110 -> 121
111 -> 122

and so on.

Your program should take an integer and output it in proper form. This is , so shortest code in bytes wins.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Is there an upper bound on input? \$\endgroup\$
    – lirtosiast
    Oct 23, 2015 at 18:48
  • 2
    \$\begingroup\$ I don't get the 109 -> 120 conversion... \$\endgroup\$ Oct 23, 2015 at 19:52
  • 7
    \$\begingroup\$ @kirbyfan64sos Since 108 maps to 109, 109 would map to the next number, which is 110. But that one has two 1s in a row, so it goes to the next number until it reaches one that does not. Which is 120, since all of 110-119 are excluded. \$\endgroup\$ Oct 23, 2015 at 19:59
  • 3
    \$\begingroup\$ @Corey Ogburn It's not about binairy. See it as how a list of numbers would be when you count up to the given number with the no-11 rule for each number in the list \$\endgroup\$
    – LukStorms
    Oct 23, 2015 at 20:26
  • 3
    \$\begingroup\$ @leymannx The number on the left represents the number in the series. So the first value in the series is 1, the second value in the series is 2, yadda yadda(lobster bisque), the tenth value in the series is 10, and the eleventh value in the series is 12, because we skipped 11 as talex finds it an abomination unto the lord. This idea continues on, hence why the 108th value in the series is 109, and the 110th value in the series is 120, as we skip everything from 110 to 119. Hope I clarified well enough. \$\endgroup\$
    – ahall
    Oct 24, 2015 at 23:35

26 Answers 26

11
\$\begingroup\$

Bash + GNU utils, 36

seq $1$1|grep -v 11|sed -n "$1{p;q}"

Try it Online

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Surely 1$1 suffices, rather than $1$1? \$\endgroup\$
    – Neil
    Oct 24, 2015 at 10:39
9
\$\begingroup\$

Burlesque, 10 bytes

{11~[n!}FO

Older versions:

ro{11~[n!}f[

ro{Sh"11"~=n!}f[
\$\endgroup\$
2
  • \$\begingroup\$ Please add a link the the language :) \$\endgroup\$
    – user42643
    Oct 23, 2015 at 20:12
  • \$\begingroup\$ done. It's been around since 2012, there's also an article on RosettaCode and the esowiki as well. \$\endgroup\$
    – mroman
    Oct 23, 2015 at 21:00
9
\$\begingroup\$

Jelly, 8 bytes

1w11¬$#Ṫ

Try it online!

Almost entirely printable ASCII! Takes input from STDIN

How it works

1w11¬$#Ṫ - Main link. No arguments
     $   - Group the previous 2 links into a monad f(k):
  11     -   Yield 11
 w       -   Yield 1 if 11 is a sublist of k's digit else 0
    ¬    -   Map 1 to 0 and 0 to 1
1     #  - Count up k = 1, 2, 3, ... until n integers return true under f(k)
       Ṫ - Return the last k

Jelly, 8 bytes

²wÐḟ11ị@

Try it online!

An alternate approach, still only 8 bytes though. Relies on the assumption that the output is always less than the square of the input

How it works

²wÐḟ11ị@ - Main link. Takes n on the left
²        - n²
  Ðḟ     - Filter-false the range [1, 2, ..., n²] on:
    11   -   11
 w       -   Is a sublist of the digits
      ị@ - Take the n'th value in this list
\$\endgroup\$
3
  • \$\begingroup\$ The assumption in your second answer is not correct, see A322054. f(A322054(n)) = 10^n and f(A322054(n))/10^n converges to 0. \$\endgroup\$
    – ovs
    Nov 12, 2020 at 15:41
  • \$\begingroup\$ @ovs How about \$n^2\$ as an upper bound? Also, yep, I'm an idiot, fixed \$\endgroup\$ Nov 12, 2020 at 15:45
  • \$\begingroup\$ \$n^2\$ seems to work. FYI your original assumption would have failed at around \$12\cdot10^{73}\$. \$\endgroup\$
    – ovs
    Nov 12, 2020 at 15:52
8
\$\begingroup\$

JavaScript, 53 bytes

n=>[...Array(n*2).keys()].filter(a=>!/11/.test(a))[n]

Alternate (using comprehensions, same length):

n=>[for(i of Array(n*2).keys())if(!/11/.test(i))i][n]
\$\endgroup\$
7
8
\$\begingroup\$

Perl 5, 34 Bytes

Looping a counter and changing the occasional double-one.

map{$i++;$i=~s/11/12/}1..pop;say$i

Test

$ perl -M5.012 -e 'map{$i++;$i=~s/11/12/}1..pop;say$i' 111
$ 122
\$\endgroup\$
7
\$\begingroup\$

Python 2, 50

lambda n:[i for i in range(n*2)if'11'not in`i`][n]

An anonymous function that lists the numbers not containing 11 in order, and takes the nth one. The off-by-one error of zero-indexing cancels with the inclusion of 0 in the list.

In theory, this will fail for sufficiently high numbers where f(n)>2*n, but this shouldn't happen until n is at least 10**50.


51 bytes:

n=input();i=0
while n:i+=1;n-='11'not in`i`
print i

Counts up numbers i until the quota of n numbers without 11 is met.

A function is the same length because of the off-by-one corrections needed.

f=lambda n,i=0:n+1and f(n-('11'not in`i`),i+1)or~-i
\$\endgroup\$
7
\$\begingroup\$

Pyth, 13 11 bytes

e.f!}`hT`ZQ

Saved 2 bytes thanks to @FryAmTheEggman.

Live demo and test cases.

13-byte version

e.f!}"11"+ZkQ
\$\endgroup\$
2
  • \$\begingroup\$ Context: Pyth, Pyth, and Pyth. \$\endgroup\$ Oct 25, 2015 at 16:21
  • \$\begingroup\$ @PeterMortensen The third one is unrelated to the Pyth used here - it's from 8 years before this Pyth was created, actually. Pyth is just a popular name for Python inspired languages. \$\endgroup\$
    – isaacg
    Oct 26, 2015 at 9:18
5
\$\begingroup\$

Python 3 74

Still need a bit of golfing.

n=int(input())
c=0
for x in ' '*n:
 c+=1
 while'11'in str(c):c+=1
print(c)

It's pretty brute force right now.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6) 43 bytes

As an anonymous function

n=>eval('for(i=0;/11/.test(i)||n--;i++);i')

Note: the very simplest way would be 44:

n=>{for(i=0;/11/.test(i)||n--;i++);return i}

Test running the snippet below.

f=n=>eval('for(i=0;/11/.test(i)||n--;i++);i')

var o='',v=0,r,c;
for(r=0;r<30;r++)
{
  o += '<tr>';
  for(c=0;c<10;c++)
  {
  
    o += '<td>' +v + '⇨' + f(v) + '</td>';
    v++;
  }
  o += '</tr>'

}
O.innerHTML=o
<table id=O style='font-size:80%'></table>

\$\endgroup\$
3
  • \$\begingroup\$ This fails for entering 108, it returns 119 \$\endgroup\$ Nov 12, 2020 at 16:33
  • \$\begingroup\$ @Samathingamajig you're right, I stand corrected after 5 years, better late than never. Should work now \$\endgroup\$
    – edc65
    Nov 13, 2020 at 13:49
  • \$\begingroup\$ 41 n=>eval('for(i=0;/11/.test(i)||n--;)++i'), not supporting 0 \$\endgroup\$
    – l4m2
    Mar 23 at 23:16
4
\$\begingroup\$

Haskell, 51 bytes

([x|x<-[0..],notElem('1','1')$zip=<<tail$show x]!!)

Usage example: ([x|x<-[0..],notElem('1','1')$zip=<<tail$show x]!!) 110 -> 121.

How it works:

[x|x<-[0..]                                   ]    -- take all x starting with 0
           ,                                       -- where
                   ('1','1')                       -- the pair of two chars '1'
            notElem                                -- is not part of
                             zip=<<tail            -- the list of pairs of neighbor elements of
                                        show x     -- the string representation of x
                                               !!  -- take nth element, where n is the parameter
\$\endgroup\$
3
\$\begingroup\$

MUMPS, 37 bytes

t(i) f j=1:1 s:j'[11 k=k+1 q:k=i
    q j

Pretty straightforward. The only "interesting" thing here is the construct j'[11 - '[ is the "does not contain" operator, so that "abc"'["ab" is false and "abc"'["cd" is true. Despite both operands of j'[11 being numbers, MUMPS remains unperturbed. It will happily autocoerce both operands to strings and move on with its life. Hooray!

(Incidentally, if you're okay with the program never terminating, we can shorten this to 35 bytes: t2(i) f j=1:1 s:j'[11 k=k+1 w:k=i j)

\$\endgroup\$
3
\$\begingroup\$

Brachylog, 15 bytes

∧{ℕ₁≜¬s11&}ᶠ↖?t

Try it online!

∧{ℕ₁≜¬s11&}ᶠ↖?t
∧{ …      }ᶠ↖?t get the N'th output from …
  ℕ₁≜             try a number, starting with 1
     ¬s11         doesn't contain 11
         &        output that number
\$\endgroup\$
3
\$\begingroup\$

GolfScript, 29 24 18 bytes

~0\{{).`11`?)}do}*

Try it online!

This is my first code golf, so this is probably the least effecient way of doing things

-5 bytes by not being dumb and using the increment symbol as well as just keeping the input on the stack and decrementing instead of wasting space saving it as a variable and comparing it, probably more things I could save on

-6 bytes the loop is fixed size and I don't need the input after the loop so I can just use repeat

\$\endgroup\$
3
\$\begingroup\$

05AB1E (legacy), 7 6 bytes

µN11å≠

-1 byte switching to the legacy version of 05AB1E, where the index is output implicitly after a while-loop µ. In the new 05AB1E version we have to push the N explicitly, and it'll output the top of the stack after the while-loop instead (so the N would be NN or ND).

Try it online or verify all test cases.

Explanation:

µ       # Loop until the counter_variable is equal to the (implicit) input-integer:
        # (the counter_variable is 0 by default)
 N11å   #  Check if the 0-based loop-index `N` contains 11 as substring
     ≠  #  Invert this boolean (1→0; 0→1)
        #  (implicitly pop the top of the stack, and increase the counter_variable by
        #  1 if it's truthy)
        # (after which the index `N` is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 05AB1E's µ is like a much better version of Jelly's # :/ \$\endgroup\$ Nov 12, 2020 at 14:34
  • \$\begingroup\$ @cairdcoinheringaahing Yeah, it's pretty useful for challenges like this. Especially that it by default increases the counter_variable at the end of every iteration if the top is truthy. \$\endgroup\$ Nov 12, 2020 at 14:42
2
\$\begingroup\$

Perl 5, 47 bytes

@_[$_]=++$i!~/11/?$i:redo for 1..<>;print$_[-1]
\$\endgroup\$
2
\$\begingroup\$

PHP, 43 bytes

while(preg_match('/11/',$i)){$i++;}print$i;
\$\endgroup\$
2
\$\begingroup\$

Perl 5 -p, 25 bytes

$\++while$\=~/11/||$_--}{

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Raku, 24 bytes

{grep(?1^/11/,^∞)[$_]}

Try it online!

grep(..., ^∞) filters the numbers from zero to infinity according to the given test object, and [$_] indexes into that sequence with the function argument, returning the number at that index.

/11/ matches any number whose decimal representation contains two consecutive one digits. The sense of the match can be inverted by writing True ^ /11/, where ^ creates an exclusive-or junction matcher that succeeds only if exactly one of its operands succeeds. True will always succeed, so the overall junction can only succeed if the /11/ fails. Finally, True can be expressed more concisely as ?1, that is, 1 coerced to a Boolean.

none(/11/) also works as a matcher, but is longer.

\$\endgroup\$
2
\$\begingroup\$

Husk, 11 10 bytes

Edit: -1 byte thanks to Razetime

!fö¬€ḋ3QdN

Try it online!

Finds index of input among natural numbers filtered to exclude those with digit-sublists that include [1,1].

\$\endgroup\$
2
  • \$\begingroup\$ -1 \$\endgroup\$
    – Razetime
    Nov 13, 2020 at 17:28
  • \$\begingroup\$ Very clever! Thanks! \$\endgroup\$ Nov 13, 2020 at 23:01
2
\$\begingroup\$

AWK, 33 bytes

{for(;$1;)$1-=!index(++b,11)}$0=b

Try it online!

It works by running a loop that increments a counter blindly each iteration, but only decrements the control variable if the blind counter does NOT include the string 11. Once the loop exits, the blind counter is printed as the answer.

 {                            }     - code block run for each input line
  for(;$1;)                         - loop until $1 is 0
           $1-=!index(   ,11)       - decrement $1 if "b" doesn't include "11"
                      ++b           - blindly increment a counter
                               $0=b - set $0 to blind count, prints automatically
\$\endgroup\$
2
\$\begingroup\$

Japt, 9 8 bytes

È¥srB}iU

Try it

\$\endgroup\$
2
\$\begingroup\$

Julia 1.0, 44 42 bytes

x->(r=1:9x)[.!occursin.("11",repr.(r))][x]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3, 64 bytes

[print(e) for e in map(str,range(int(input())+1))if not'11'in e]

Try it online!

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

Java (JDK), 76 bytes

p->{int c=1,s=0;while((c+s+"").indexOf("11")>=0&&++s>0||c++<p);return p+s;};

Try it online!

How it works: Lambda function obviously, but mostly it uses short-circuit logic in the while loop boolean to increment the appropriate counter keeping track of the cumulative shift for each input and returning the input plus that shift.

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

Excel, 64 bytes

=LET(x,SEQUENCE(2^20),INDEX(FILTER(x,ISERROR(FIND("11",x))),I7))

Works up to 1,000,579 -> 1,048,576

\$\endgroup\$
1
  • \$\begingroup\$ you don't actually need the "s in Find() \$\endgroup\$ Jan 10 at 16:30
0
\$\begingroup\$

Pip, 11 bytes

LaW11N Ui_i

Attempt This Online!

Explanation

             i is 0; a is first command-line argument (implicit)
La           Loop (a) times:
  W           Loop while
   11N        11 is a substring of
       Ui     i, incremented:
         _     No-op
          i  Once the loop completes, output i
\$\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.