Detect the Zeroless Numbers

16

3

Zeroless numbers are numbers that do not contain 0 as one of their decimal digits.

Given an integer K, return the Kth zeroless number. K will be non-negative if you choose 0-indexing, or positive if you choose 1-indexing instead. Note that this is OEIS A052382.

This is code golf, so the shortest code in bytes wins.

Test cases

1-indexed:

1 -> 1
2 -> 2
9 -> 9
10 -> 11
16 -> 17
100 -> 121

0-indexed:

0 -> 1
1 -> 2
8 -> 9
9 -> 11
15 -> 17
99 -> 121

user74686

Posted 2017-10-12T14:48:23.540

Reputation:

Question was closed 2017-10-14T15:45:43.267

5Converting n to bijective base 10 is fundamentally the same as counting in bijective base B, so by the standards of PPCG this is a duplicate. – Peter Taylor – 2017-10-12T20:20:57.397

4@PeterTaylor I wouldn't say this is a duplicate, since here much simpler approaches are possible, like counting up and discarding numbers containing a 0 (and seeing different ways to check if a number contains a 0 is interesting by itself) – Leo – 2017-10-12T20:57:08.617

2@Leo, that approach is possible in the other question too. – Peter Taylor – 2017-10-12T21:42:47.640

1@PeterTaylor it may be possible, but it is not competitive there. Of the answers I can understand in the other question, none use this approach. The vast majority of them are based on cartesian product, which could also be applicable here but currently seems inferior to the other approaches. – Leo – 2017-10-12T22:29:21.750

The way I see it is, convert k (zero indexed) into base 9, in the string of digits add 1 to each (and interpret the string as a number in base 10). That seems to be an efficient way time-wise, but won't necessarily make shorter code, depending on the language's features, so brute force may be shorter... – Heimdall – 2017-10-13T13:39:36.180

@Heimdall this doesn't work, e.g. 99 is 120 in base 9, so your method would yield 231. what works is converto the 1-indexed k into base 9, and starting from the most significant digit, replace every 0 you encounter with a 9 and then subtract 1 from the group of digits to the left of your current digit. – Felix Palmen – 2017-10-13T13:52:53.633

@FelixPalmen I see the flaw in my method, it doesn't give numbers that begin with 1. I should use a hybrid system where the most significant digit is is base 10 and the rest of the number is in base 9 (but then I wouldn't be able to use a built-in base converter if there is one in whichever language I go for, I would have to write my own). Then leave the most significant digit alone and add 1 to all other digits (if any). Of course, that would need 1-indexed k. – Heimdall – 2017-10-15T04:56:54.583

@FelixPalmen Your method is good though, applied carefully. You could just subtract 1 from the digit to the left rather than the group because it's not going to be 0 since you're parsing from left (from the most significant digit. But sometimes you'll create more zeroes because you'll subtract 1 from 1 (which I guess you'll ignore if that 1 was the most significant digit, like with k=1). So those additional zeroes will have to be dealt with, too, maybe immediately, and continue to parse the number after dealing with the additional zero, or parse the number again. – Heimdall – 2017-10-15T04:59:19.700

For example, k=66348, in base 9 it is 111010. First zero is the fourth digit, so it becomes 110910. Continue parsing the number, the next zero is the sixth (last) digit, we get 110909. Because we created more zeroes, we do another parse (or we have remembered where they were, positions 3 and 5). We get 109909, 109899, next parse, 099899; as it's the most significant number that became 0, we just drop it -> 99899. Or if newly created zeroes are dealt with immediately, it's just one parse: find first zero on position 4, 111010 -> 110910 -> 109910 -> (0)99910, find next zero, -> 99909 -> 99899. – Heimdall – 2017-10-15T05:37:25.350

@Heimdall the latter is the algorithm my submission uses ;) This is effectively "subtracting 1 from the group of digits to the left" with the special rule that for the most significant digit only, 0 isn't wrapped to 9 but "cut off" instead. Of course, doing multiple adjustment passes would work as well, didn't think of that. I might check whether it buys me bytes :) – Felix Palmen – 2017-10-15T07:39:55.123

@WheatWizard This can't be a duplicate. If you solve this with a base conversion, adjusting the resulting digits is quite a bit more complex than in the linked challenge. Also, as already commented, other solutions than a base conversion are possible and, depending on the language, superior here. – Felix Palmen – 2017-10-15T07:43:41.540

2@felixpalmen I disagree. I think this is a duplicate. I'm quite tired of this general attitude that nothing is a duplicate because of minor differences in the approach of language X. Your free top vote to reopen but I'm not changing my vote. – Post Rock Garf Hunter – 2017-10-15T16:08:08.830

2@WheatWizard I'm quite tired of people spoiling challenges because of faint similarities. The differences here are substantial. – Felix Palmen – 2017-10-16T05:09:50.893

Answers

28

Jelly, 3 bytes

ḃ9Ḍ

Try it online!

How it works

ḃ9Ḍ  Main link. Argument: n (1-based index)

ḃ9   Convert n to bijective base 9.
  Ḍ  Convert the result from base 10 to integer.

Dennis

Posted 2017-10-12T14:48:23.540

Reputation: 196 637

6whoa this is actually genius +1 – HyperNeutrino – 2017-10-12T15:05:21.270

6Langs with 'monads' and 'bijectives' and 'trilithiums' make me feel like a doofus. – Nick T – 2017-10-12T17:23:53.490

I'm sorry if this is old news and is addressed elsewhere, i'm new, but wouldn't that be 3 characters? – Robbie Mckennie – 2017-10-13T10:23:18.780

1

@RobbieMckennie Jelly, as with several other golfing language, has its own code page so that each character is only one byte long. This program would be E7 39 C1 (invalid in UTF-8.)

– LegionMammal978 – 2017-10-13T11:09:58.580

Aaaahh got you. – Robbie Mckennie – 2017-10-13T13:02:29.157

13

Python 2, 35 bytes

f=lambda n:n and~-n%9+1+f(~-n/9)*10

Try it online!

One indexed.

xnor

Posted 2017-10-12T14:48:23.540

Reputation: 115 687

lambda n:int(str(n),11) is shorter. – 0WJYxW9FMN – 2017-12-27T11:17:09.650

@J843136028 That gives outputs containing zeroes. – xnor – 2017-12-27T23:40:29.413

5

Python 2, 50 bytes

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

Try it online!

TFeld

Posted 2017-10-12T14:48:23.540

Reputation: 19 246

5

Actually, 10 bytes

⌠$'0@cY⌡╓N

Try it online!

Explanation:

⌠$'0@cY⌡╓N
⌠      ⌡╓N  nth number (starting with i=0) where
 $            string representation of i
  '0@cY       does not contain 0

Mego

Posted 2017-10-12T14:48:23.540

Reputation: 32 998

5

Haskell, 31 bytes

(filter(all(>'0').show)[0..]!!)

Try it online!

32 bytes

(l!!)
l=(+).(10*)<$>0:l<*>[1..9]

Try it online! One-indexed.

33 bytes

(l!!)
l=0:[10*a+b|a<-l,b<-[1..9]]

Try it online!

34 bytes

(l!!)
l=0:do a<-l;take 9[10*a+1..]

Try it online!

37 bytes

f 0=0
f n=mod(n-1)9+1+10*f(div(n-1)9)

Try it online!

xnor

Posted 2017-10-12T14:48:23.540

Reputation: 115 687

5

Perl 5, 20 bytes

19 bytes code + 1 for -p.

Uses 1-indexing.

0while$_-=++$\!~0}{

Try it online!

Dom Hastings

Posted 2017-10-12T14:48:23.540

Reputation: 16 415

5

Javascript (ES7), 23 Bytes

f=n=>n&&n--%9+10*f(n/9)

Explanation:

f=n=>                  //=> syntax
     n&&n--%9          //only with 0 0s
             +10*f(n/9)//^^

user75200

Posted 2017-10-12T14:48:23.540

Reputation: 141

Welcome to the site! :) – James – 2017-10-12T19:34:59.423

3Hello! 17B if you use: n=>+n.toString(9) (anonymous functions are allowed) – Ephellon Dantzler – 2017-10-12T21:20:47.147

4

Python 2, 50 bytes

n=input();v=0
while n:v+=1;n-=min(`v`)>'0'
print v

Try it online!

ovs

Posted 2017-10-12T14:48:23.540

Reputation: 21 408

4

PowerShell, 40 bytes

param($a)(1..(2*$a)|?{$_-notmatch0})[$a]

Try it online!

Take input $a, then construct a range from 1 to 2*$a. Pull out those elements that regex do -notmatch 0, and then take the $ath one thereof. Output is implicit.

AdmBorkBork

Posted 2017-10-12T14:48:23.540

Reputation: 41 581

4

Haskell, 31 bytes

This is zero-indexed

(filter(all(>'0').show)[1..]!!)

Try it online!

H.PWiz

Posted 2017-10-12T14:48:23.540

Reputation: 10 962

4

MATL, 16 13 14 bytes

-2 bytes thanks to Luis Mendo

E:!tV48-!XA)G)

Try it online!

Explanation:

(implicit input)
E                   % double
 :                  % 1:top of stack (so [1, 2, ..., 2n])
  !t                % transpose and dup
    V               % cast to chars
     48-            % subtract 48 (maps numbers to digits)
        !           % transpose
         XA         % Check each column if All are true (nonzero)
           )        % index into array (so we are left with zeroless numbers)
            G)      % paste input and index; TOS is the nth element.
(implicit output)

Giuseppe

Posted 2017-10-12T14:48:23.540

Reputation: 21 077

3

Jelly, 5 bytes

DȦ$#Ṫ

-2 bytes thanks to Dennis

Explanation

DȦ$#Ṫ  Main link; takes input from STDIN
   #   nfind; get first n matches starting from 0
  $    Get numbers that are zeroless:
D      Digits
 Ȧ     Are all truthy
    Ṫ  Tail; get last element

Try it online!

HyperNeutrino

Posted 2017-10-12T14:48:23.540

Reputation: 26 575

3

05AB1E, 5 bytes

µNSĀP

Try it online!

Explanation

µ       # loop over N until input matches are found
 NS     # split N into list of digits
   Ā    # check if trueish (not zero)
    P   # product

or with Dennis's base conversion trick

05AB1E, 3 bytes

9.h

Try it online!

Emigna

Posted 2017-10-12T14:48:23.540

Reputation: 50 798

2Ahhhh!!! We let Jelly use base conversion before 05AB1E! Noooooooo o's trail off into the distance... – Magic Octopus Urn – 2017-10-12T17:16:43.860

2

Pyth,  9  8 bytes

e.f*FjZT

Verify all the test cases.

Explanation

e.f*FjZT   ~ Full program.

 .f        ~ Collect the first Q matches. Uses a variable Z.
     jZT   ~ Decimal digits of Z.
   *F      ~ Product. Can be replaced by .A (all) - Basically checks if all are ≥ 1.
e          ~ End. Get the last element.

Mr. Xcoder

Posted 2017-10-12T14:48:23.540

Reputation: 39 774

2

QBIC, 32 bytes

[:|p=p+1≈instr(!p$,@0`)|p=p+1}?p

Explanation

[:|     FOR a = 1 to <input>
p=p+1   increase p (starts as 0) by 1
≈       WHILE
 instr  the index in 
 (!p$     the string-cast of p
 ,@0`)|   of the string '0' is non-zero
 p=p+1    skip this number in the zero-less sequence
}       WEND, NEXT 
?p      PRINT p

steenbergh

Posted 2017-10-12T14:48:23.540

Reputation: 7 772

2

Mathematica, 55 bytes

(s=t=1;While[s<=#,If[DigitCount[t++,10,0]<1,s++]];t-1)&

Try it online!

J42161217

Posted 2017-10-12T14:48:23.540

Reputation: 15 931

2

6502 machine code (C64), 124 bytes

00 C0 20 FD AE 20 6B A9 A2 05 A9 00 85 FB 85 FC 85 FD A0 10 06 FB 06 14 26 15
90 02 E6 FB A5 FB C9 09 90 04 E9 09 85 FB 26 FC 26 FD 88 D0 E5 A5 FB 95 61 CA
A5 FD 85 15 A5 FC 85 14 D0 CC A5 15 D0 C8 E8 86 FE B5 61 D0 1E A9 09 95 61 86
9E CA B4 61 F0 11 D6 61 D0 0D E4 FE D0 04 E6 FE B0 05 95 61 CA 10 EB A6 9E E8
E0 06 D0 D9 18 A6 FE B5 61 69 30 20 D2 FF E8 E0 06 D0 F4 60

Online demo

Usage: sys49152,[n], e.g. sys49152,100. n is 1-indexed.

Valid values are in the range [1,63999].

Explanation:

The common approach to save bytes is to do it iteratively / recursively checking for decimal 0 digits -- this doesn't save bytes on the C64 because there's not even a division instruction available -- just converting to base 9 and adjusting the digits gives a shorter result (still with the need to hand-code a long binary division). Here's the commented disassembly:

         00 C0       .WORD $C000        ; load address
.C:c000  20 FD AE    JSR $AEFD          ; consume comma
.C:c003  20 6B A9    JSR $A96B          ; read 16bit number
.C:c006  A2 05       LDX #$05           ; index of last digit in result
.C:c008   .divide:
.C:c008  A9 00       LDA #$00           ; initialize some variables
.C:c00a  85 FB       STA $FB            ; to zero ...
.C:c00c  85 FC       STA $FC
.C:c00e  85 FD       STA $FD
.C:c010  A0 10       LDY #$10           ; repeat 16 times for division
.C:c012   .div_loop:
.C:c012  06 FB       ASL $FB            ; shift remainder left
.C:c014  06 14       ASL $14            ; shift dividend ...
.C:c016  26 15       ROL $15            ; ... left
.C:c018  90 02       BCC .div_nobit     ; highest bit set?
.C:c01a  E6 FB       INC $FB            ; then add one to remainder
.C:c01c   .div_nobit:
.C:c01c  A5 FB       LDA $FB            ; compare remainder ...
.C:c01e  C9 09       CMP #$09           ; ... to 9 (divisor)
.C:c020  90 04       BCC .div_nosub     ; if greater or equal 9 (divisor)
.C:c022  E9 09       SBC #$09           ; subtract 9 from remainder
.C:c024  85 FB       STA $FB
.C:c026   .div_nosub:
.C:c026  26 FC       ROL $FC            ; shift quotient left, shifting in
.C:c028  26 FD       ROL $FD            ; carry if remainder was >= 9
.C:c02a  88          DEY                ; loop counting
.C:c02b  D0 E5       BNE .div_loop      ; and repeat
.C:c02d  A5 FB       LDA $FB            ; load remainder
.C:c02f  95 61       STA $61,X          ; store in current output digit
.C:c031  CA          DEX                ; decrement digit index
.C:c032  A5 FD       LDA $FD            ; copy quotient ...
.C:c034  85 15       STA $15
.C:c036  A5 FC       LDA $FC            ; ... to dividend
.C:c038  85 14       STA $14
.C:c03a  D0 CC       BNE .divide        ; if not zero yet
.C:c03c  A5 15       LDA $15
.C:c03e  D0 C8       BNE .divide        ; repeat division by 9
.C:c040  E8          INX
.C:c041  86 FE       STX $FE            ; remember index of first digit
.C:c043   .adjust_loop:
.C:c043  B5 61       LDA $61,X          ; load digit
.C:c045  D0 1E       BNE .nonine        ; if it's zero, must be changed to 9
.C:c047  A9 09       LDA #$09
.C:c049  95 61       STA $61,X
.C:c04b  86 9E       STX $9E            ; save current index and go back
.C:c04d  CA          DEX
.C:c04e   .sub_loop:
.C:c04e  B4 61       LDY $61,X          ; examine previous digit
.C:c050  F0 11       BEQ .sub_done      ; zero? nothing more to subtract
.C:c052  D6 61       DEC $61,X          ; decrement previous digit
.C:c054  D0 0D       BNE .sub_done      ; not zero -> done
.C:c056  E4 FE       CPX $FE            ; are we at the first digit?
.C:c058  D0 04       BNE .sub_next      ; no: go on
.C:c05a  E6 FE       INC $FE            ; first digit now zero, so increment
.C:c05c  B0 05       BCS .sub_done      ; and done with subtraction
.C:c05e   .sub_next:
.C:c05e  95 61       STA $61,X          ; store 9 to this digit
.C:c060  CA          DEX                ; and go to previous
.C:c061  10 EB       BPL .sub_loop      ; repeat
.C:c063   .sub_done:
.C:c063  A6 9E       LDX $9E            ; load saved digit index
.C:c065   .nonine:
.C:c065  E8          INX
.C:c066  E0 06       CPX #$06           ; reached last digit?
.C:c068  D0 D9       BNE .adjust_loop   ; no -> repeat
.C:c06a  18          CLC
.C:c06b  A6 FE       LDX $FE            ; start output at first digit
.C:c06d   .out_loop:
.C:c06d  B5 61       LDA $61,X          ; load digit
.C:c06f  69 30       ADC #$30           ; add character code `0`
.C:c071  20 D2 FF    JSR $FFD2          ; output character
.C:c074  E8          INX                ; next
.C:c075  E0 06       CPX #$06           ; last digit done?
.C:c077  D0 F4       BNE .out_loop      ; if not, repeat
.C:c079  60          RTS

Felix Palmen

Posted 2017-10-12T14:48:23.540

Reputation: 3 866

2

Perl 6, 24 bytes

{(grep {!/0/},^∞)[$_]}

Try it online!

0-indexed.

Sean

Posted 2017-10-12T14:48:23.540

Reputation: 4 136

grep(…) will be one character shorter than (grep …). Otherwise it is basically the same as I came up with. (I used 1..*) – Brad Gilbert b2gills – 2017-10-14T15:30:28.257

1

Python 2, 50 49 bytes

1 byte off thanks to @Mr.Xcoder

lambda n:[k for k in range(2*n)if('0'in`k`)<1][n]

0-based.

Try it online!

Luis Mendo

Posted 2017-10-12T14:48:23.540

Reputation: 87 464

1

C, 70 bytes

i,j,k;f(n){for(i=0;n--;n+=!k)for(k=j=++i;j;j/=10)k=j%10?k:0;return i;}

1-indexed

Try it online!

C (gcc), 65 bytes

i,j,k;f(n){for(i=0;n--;n+=!k)for(k=j=++i;j;j/=10)k=j%10?k:0;n=i;}

1-indexed

Try it online!

Steadybox

Posted 2017-10-12T14:48:23.540

Reputation: 15 798

1

JavaScript (ES6), 28 27 bytes

f=n=>n&&--n%9+1+10*f(n/9|0)
<input type=number min=1 oninput=o.textContent=f(this.value)><pre id=o>

Edit: Saved 1 byte by switching to a numeric result (effectively porting @xnor's Python answer).

Neil

Posted 2017-10-12T14:48:23.540

Reputation: 95 035

1

Excel VBA, 57 Bytes

Anonymous VBE immediate window function that takes input, n from range [A1] and outputs the nth 0-indexed zeroless number to the VBE immediate window. 

For i=1To[A1]:j=j+1:While InStr(1,j,0):j=j+1:Wend:Next:?j

Taylor Scott

Posted 2017-10-12T14:48:23.540

Reputation: 6 709

1

AWK, 39 bytes

{for(;c<$1;)c=index(++i,0)?c:c+1;$0=i}1

Since this is AWK 1-indexing seemed appropriate.

Try it online!

Robert Benson

Posted 2017-10-12T14:48:23.540

Reputation: 1 339

1

Java 8, 45 bytes

int c(int n){return n>0?--n%9+1+c(n/9)*10:0;}

1-indexed

Port of @xnor's Python 2 answer.

Explanation:

Try it here.

int c(int n){  // Method with integer as both parameter and return-type
  return n>0?  //  If `n` is larger than 0:
    --n%9      //   Return `(n-1)%9
    +1         //    + 1
    +c(n/9)    //    + recursive call with `(n-1)/9`
     *10       //      multiplied by 10
   :           //  Else:
    0;         //   Return 0
}              // End of method

Kevin Cruijssen

Posted 2017-10-12T14:48:23.540

Reputation: 67 575

1

C# (.NET Core), 68 63 bytes

-8 bytes thanks to @raznagul.

k=>{int i=0;for(;k>0;)if(!(++i+"").Contains("0"))k--;return i;}

Try it online!

Don't really want to use this, since it's just a C# port of an existing answer.

C# (.NET Core), 45 bytes

int c(int n){return n>0?--n%9+1+c(n/9)*10:0;}

Try it online!

Ian H.

Posted 2017-10-12T14:48:23.540

Reputation: 2 431

You can save some bytes by removing j and decrementing k instead. – raznagul – 2017-10-14T11:24:27.703

1

Jq 1.5, 76 bytes

[.,0]|until(.[0]<1;.[1]+=1|if"\(.[1])"|contains("0")then. else.[0]-=1end)[1]

Expanded

  [.,0]                           # initial state (n, v)
| until(.[0]<1;                   # until we've found n'th number
     .[1]+=1                      #   increment v
   | if "\(.[1])"|contains("0")   #   if v contains 0
     then .                       #   leave state alone
     else .[0]-=1                 #   otherwise decrement n
     end
  )[1]                            # return n'th number found

Try it online!

jq170727

Posted 2017-10-12T14:48:23.540

Reputation: 411

Asked: 2017-10-12T14:48:23.540

Viewed: 2 629 times

Active: 2017-10-14T18:09:40.093