Count without 3

Question

Background

When I was in elementary school, we used to play a game in math class that goes as follows.

All kids sit in a big circle and take turns counting, starting from 1.

However, the following numbers must be skipped while counting:

• Numbers that are multiples of 3.
• Numbers that have a 3 in its decimal representation.

The first 15 numbers the kids should say are

1 2 4 5 7 8 10 11 14 16 17 19 20 22 25

Whenever somebody gets a number wrong – says a number that isn't in the sequence or skips a number that is – he's removed from the circle. This goes on until there's only one kid left.

Task

You're bad at this game, so you decide to cheat. Write a program or a function that, given a number of the sequence, calculates the next number of the sequence.

You don't have to handle numbers that cannot be represented using your language's native numeric type, provided that your program works correctly up to input 251 and that your algorithm works for arbitrarily large inputs.

Input and output can use any convenient base.

Since you have to conceal your code, it must be as short as possible. In fact, this is code-golf, so the shortest code in bytes wins.

Test cases

  1 ->   2
  2 ->   4
 11 ->  14
 22 ->  25
 29 ->  40
251 -> 254

Answer 1

Brachylog, 10 bytes

<.='e3:I'*

Try it online!

Explanation

(?)<.                Output > Input
    .=               Assign a value to the Output
    . 'e3            3 cannot be an element of the Output (i.e. one of its digits)
        3:I'*(.)     There is no I such that 3*I = Output

Answer 2

JavaScript (ES6), 30 bytes

f=n=>++n%3*!/3/.test(n)?n:f(n)

Answer 3

Python 2, 73 66 43 bytes

Thanks to xnor for telling me I was being silly by using 2 variables, and thanks to Mitch Schwartz too.

x=~input()
while'3'[:x%3]in`x`:x-=1
print-x

Answer 4

J, 24 bytes

3(]0&({$:)~e.&":+.0=|)>:

Straight-forward approach that just iterates forward from input n until it finds the next number that is valid by the rules.

Forms five smileys, $:, :), 0=, =|, and >:.

Usage

   f =: 3(]0&({$:)~e.&":+.0=|)>:
   (,.f"0) 1 2 11 22 29 251
  1   2
  2   4
 11  14
 22  25
 29  40
251 254

Explanation

3(]0&({$:)~e.&":+.0=|)>:  Input: integer n
                      >:  Increment n
3                         The constant 3
 (                   )    Operate dyadically with 3 (LHS) and n+1 (RHS)
                    |       Take (n+1) mod 3
                  0=        Test if equal to 0
             &":            Format both 3 and n+1 as a string
           e.               Test if it contains '3' in str(n+1)
                +.          Logical OR the results from those two tests
  ]                         Right identity, gets n+1
   0&(   )~                 If the result from logical OR is true
       $:                     Call recursively on n+1
      {                       Return that as the result
                            Else act as identity function and return n+1

Answer 5

05AB1E, 11 bytes

[>Ð3ås3Ö~_#

Try it online!

Explanation

               # implicit input
[              # start loop
 >             # increase current number
  Ð            # triplicate
          #    # break loop IF
         _     # logical negation of
   3å          # number has one or more 3's in it
        ~      # OR
     s3Ö       # number % 3 == 0

Answer 6

Perl, 19 bytes

18 bytes code + 1 for -p.

++$_%3&&!/3/||redo

Usage

perl -pe '++$_%3&&!/3/||redo' <<< 8
10

perl -pe '++$_%3&&!/3/||redo' <<< 11
14

Answer 7

Java 8, 57 56 55 50 bytes

Thanks to @Numberknot for 1 byte Thanks to @Kevin Cruijssen for 5 bytes

i->{for(;++i%3<1|(i+"").contains("3"););return i;}

This is a Function<Integer, Integer>

Explanation

Naive implementation that simply increments until it reaches an acceptable number.

Test Class

public class CodeGolf {

    public static void main(String[] args) {
        Function<Integer, Integer> countingGame = i->{for(;++i%3<1|(i+"").contains("3"););return i;};
        int val = 1;
        for (int i = 0; i < 10; i++) {
            System.out.print(val + " ");
            val = countingGame.apply(val);
        }
    }

}

Output of Test Class:

1 2 4 5 7 8 10 11 14 16

Answer 8

Japt, 18 bytes

°U%3*!Us f'3 ?U:ßU

Test it online

I finally have a chance to use ß :-)

How it works

                    // Implicit: U = input integer
°U%3                // Increment U, and take its modulo by 3.
     !Us f'3        // Take all matches of /3/ in the number, then take logical NOT.
                    // This returns true if the number does not contain a 3.
    *               // Multiply. Returns 0 if U%3 === 0  or the number contains a 3.
             ?U     // If this is truthy (non-zero), return U.
               :ßU  // Otherwise, return the result of running the program again on U.
                    // Implicit: output last expression

Answer 9

PowerShell v2+, 46 bytes

for($a=$args[0]+1;$a-match3-or!($a%3)){$a++}$a

Takes input $args[0], adds 1, saves into $a, starts a for loop. The conditional keeps the loop going while either $a-match3 (regex match) -or $a%3 is zero (the ! of which is 1). The loop simply increments $a++. At the end of the loop, we simply place $a on the pipeline, and output via implicit Write-Output happens at program completion.

Examples

PS C:\Tools\Scripts\golfing> 1,2,11,22,29,33,102,251,254|%{"$_ --> "+(.\count-without-three.ps1 $_)}
1 --> 2
2 --> 4
11 --> 14
22 --> 25
29 --> 40
33 --> 40
102 --> 104
251 --> 254
254 --> 256

Answer 10

R, 46 bytes

n=scan()+1;while(!n%%3|grepl(3,n))n=n+1;cat(n)

Answer 11

Python 2, 49 44 42 bytes

f=lambda x:'3'[:~x%3]in`~x`and f(x+1)or-~x

The other Python entry beats this (edit: not any more :-D), but I posted it because I rather like its recursive approach. Thanks to Mitch Schwarz and Erik the Golfer for helping me make this shorter.

Answer 12

Lua, 58 Bytes

i=...+1while(i%3==0or(i..""):find"3")do i=i+1 end print(i)

Answer 13

Pyke, 13 bytes

Whii3%!3`i`{|

Try it here!

              - i = input
W             - do:
 hi           -  i += 1
   i3%!       -    not (i % 3)
            | -   ^ or V
       3`i`{  -    "3" in str(i)
              - while ^

Answer 14

Haskell, 50 48 bytes

f n=[x|x<-[n..],mod x 3>0,notElem '3'$show x]!!1

Try it on Ideone. Saved 2 bytes thanks to @Charlie Harding.

Alternative: (50 bytes)

g=f.(+1)
f n|mod n 3<1||(elem '3'.show)n=g n|1<3=n

Answer 15

C#, 56, 51 bytes.

This is surprisingly short for a C# answer!

x=>{while(++x%3<1|(x+"").Contains("3"));return x;};

Answer 16

Pyth, 11 bytes

f&-I`T3%T3h

Try it online: Demonstration or Test Suite

Explanation:

f&-I`T3%T3hQ   implicit Q at the end
f         hQ   find the smallest integer T >= input + 1 which fulfills:
  -I`T3           T is invariant under removing the digit 3
 &                and
       %T3        T mod 3 leaves a positive remainder

Answer 17

PHP, 47 41 bytes

inspired by Xanderhall, but the latest idea finally justifies an own answer.

while(strstr($n+=$n=&$argn%3,51));echo$n;

or

while(strpbrk($n+=$n=&$argn%3,3));echo$n;

This takes advantage from the fact that the input is also from the sequence: For $n%3==1, the new modulo is 2. For $n%3==2, the new modulo is 4-3=1. $n%3==0 never happens.

Run as pipe with -R or try them online.

Answer 18

Perl 6, 27 25 24 bytes

{max $_+1...{!/3/&$_%3}}

Try it online!

Finds the first number larger than the input that doesn't have a three and has a remainder when moduloed by 3. I was hoping to do something fancy with the condition, like !/3/&*%3 but it doesn't work with the !. :(

Explanation:

{                      }   # Anonymous code block
     $_+1                  # From the input+1
         ...               # Get the series
            {         }    # That ends when
             !/3/            # The number does not contain a 3
                 &           # and
                  $_%3       # The number is not divisible by 3
 max                       # And get the last element of the series

Answer 19

APL (Dyalog Unicode), 33 28 27 19 bytes^SBCS

1∘+⍣{('3'∊⍕⍺)<×3|⍺}

Try it online!

-6 thanks to Adám. -8 thanks to ngn.

Old Explanation:

1-⍨g⍣((×3|⊢)>'3'∊⍕)∘(g←+∘1)
                       +∘1  ⍝ curry + with 1, gives the increment function
                            ⍝ increments the left argument so we do not return the number itself
                    (g←   ) ⍝ assign to "g"
                   ∘        ⍝ compose g with the repeat
                 ⍕          ⍝ does parsing the argument to a string...
             '3'∊           ⍝ ...contain '3'?
        3|⊢                 ⍝ residue of a division by 3
      (×   )                ⍝ direction (0 if 0, 1 if greater, ¯1 is lower)
     (      >     )         ⍝ and not (we want the left side to be 1, the right side 0)
   g⍣                       ⍝ repeat "g" (increment) until this function is true ^
1-⍨                         ⍝ afterwards, decrement: inversed -

APL (Dyalog Extended), 23 17 bytes^SBCS

1∘+⍣(3(×⍤|>∊⍥⍕)⊣)

Try it online!

Thanks to Adám. -6 thanks to ngn.

Old Explanation:

0+⍣(3(×⍤|>∊⍥⍕)⊢)⍢(1+⊢)⊢
0                       ⍝ the left argument (⍺)
 +⍣(3(×⍤|>∊⍥⍕)⊢)        ⍝ the left function (⍺⍺)
                 (1+⊢)  ⍝ the right function (⍵⍵)
                        ⍝     (increments its argument)
                      ⊢ ⍝ the right argument (⍵)
                        ⍝     (just returns the input)
                ⍢       ⍝ under:
                        ⍝     calls (⍵⍵ ⍵) first, which increments the input
                        ⍝     also (⍵⍵ ⍺) which gives 1
                        ⍝     then calls (⍺incremented ⍺⍺ ⍵incremented)
                        ⍝     afterwards, does the opposite of ⍵⍵, and decrements the result
  ⍣                     ⍝ ⍣ fixpoint: repeats the left operation until the right side is truthy
 +                      ⍝ calls + with ⍺incremented and the input (so, 1+input)
   (3(×⍤|>∊⍥⍕)⊢)        ⍝ right operation
    3                   ⍝ on its left, "3"
              ⊢         ⍝ on its right, the current iteration
      ×⍤|               ⍝ divisibility check: × atop |
        |               ⍝     starts with 3|⊢ (residue of ⊢/3)
      ×                 ⍝     then returns the direction (0 if 0, 1 if greater, ¯1 is lower)
          ∊⍥⍕           ⍝ contains 3:
            ⍕           ⍝    stringifies both its arguments (3 and ⊢)
          ∊⍥            ⍝    checks for membership
         >              ⍝ divisibility "and not" contains 3

Answer 20

GolfSharp, 43 bytes

m=>r(m,m).w(n=>n%3>0&!n.t().I("3")).a()[1];

Answer 21

PHP, 60 55 54 46 bytes

Thanks to @user59178 for shaving off a few bytes, @AlexHowansky for a byte, @Titus for another few bytes

for(;strstr($i=++$argv[1],51)|$i%3<1;);echo$i;

Called from command line with -r. Naive method that loops while the number is a multiple of 3, or has 3 in its digits.

Answer 22

Ruby, 47 bytes

i=gets.to_i;i while(i+=1)%3==0||"#{i}"=~/3/;p i

I really feel like this can be golfed further.

Answer 23

MATL, 14 bytes

`Qtt3\wV51-hA~

Try it online!

Explanation

`       % Do...while
  Q     %   Add 1. Takes input implicitly in the first iteration
  tt    %   Duplicate twice
  3\    %   Modulo 3
  wV    %   Swap, string representation
  51-   %   Subtract 51, which is ASCII for '3'
  h     %   Concatenate
  A~    %   True if any result was 0. That indicates that the number
        %   was a multiple of 3 or had some '3' digit; and thus a 
        %   new iteration is needed

Answer 24

Labyrinth, 117 102 bytes

?       """""""""""_
):_3    (         0/{!@
;  %;:}_';:_3-_10 1
"  1            %;_
""""_""""""""{;;'

Try it online!

Labyrinth is a two-dimensional, stack-based programming language and at junctions, direction is determined by the top of the stack (positive goes right, negative goes left, zero goes straight). There are two main loops in this programs. The first mods the integer input by 3 and increments if 0. The second repeatedly checks if the last digit is 3 (by subtracting 3 and modding by 10) and then dividing by 10 to get a new last digit.

Answer 25

Jelly, 11 bytes

D;Æf3ḟµ‘#2ị

Try it online!

How it works

D;Æf3ḟµ‘#2ị  Main link. Argument: n

      µ      Combine the links to the left into a chain.
       ‘#    Execute the chain for k = n, n + 1, n + 2, ... until n + 1 matches
             were found. Yield the array of all n + 1 matches.
D            Decimal; yield the array of k's decimal digits.
  Æf         Yield the array of k's prime factors.
 ;           Concatenate both.
    3ḟ       Filter false; remove digits and factors from [3].
             This yields [3] (truthy) if neither digits nor factors contain 3,
             [] (falsy) if they do.
         2ị  Extract the second match. (The first match is n.)

Answer 26

Mathematica, 51 bytes

#+1//.t_/;t~Mod~3<1||!IntegerDigits@t~FreeQ~3:>t+1&

Try it online!

Answer 27

Turing Machine Code, 390 bytes

0 * * r 0
0 _ _ l 1
1 1 2 l 2
1 2 3 r 0
1 3 4 l 2
1 4 5 l 2
1 5 6 l 2
1 6 7 l 2
1 7 8 l 2
1 8 9 l 2
1 9 0 l 1
1 * 1 l 2
2 * * l 2
2 _ _ r 3
3 1 1 r 4
3 4 4 r 4
3 7 7 r 4
3 2 2 r 5
3 5 5 r 5
3 8 8 r 5
3 _ _ l 1
4 1 1 r 5
4 4 4 r 5
4 7 7 r 5
4 2 2 r 3
4 5 5 r 3
4 8 8 r 3    
5 1 1 r 3
5 4 4 r 3
5 7 7 r 3
5 2 2 r 4
5 5 5 r 4
5 8 8 r 4    
* 0 0 r *
* 6 6 r *
* 9 9 r *
* 3 3 r 0
* _ _ * halt

Try it online.

Answer 28

Stax, 9 bytes

ú╜H▌»NWì╤

Run and debug it

Unpacked, ungolfed, and commented it looks like this.

w       repeat rest of the program while the produced value is true
  ^c    increment and copy value
  E3#   (a) count number of digits that are 3
  n     copy incremented value
  3%!   (b) is multiple of 3?
  +     sum of (a) + (b) values

Run and debug this one

Answer 29

Forth (gforth), 81 bytes

: f begin 1+ >r i i 3 mod 1 r> begin 10 /mod >r 3 <> * r> ?dup 0= until * until ;

Try it online!

Explanation

1. Add 1
2. check if multiple of 3
3. check if contains a 3
4. if the result of step 3 or step 4 is true, repeat from step 1

Code Explanation

: f               \ start a new word definition
  begin           \ start an indefinite loop
    1+            \ add 1 to current number
    >r i i        \ put current number on return stack, then place on normal stack twice
    3 mod         \ check if number is multiple of 3
    1 r>          \ place a 1 on the stack, then move the current number to the normal stack
    begin         \ start another indefinite loop
      10 /mod     \ get quotient and remainder of dividing by 10
      >r          \ put quotient on return stack
      3 <>        \ check if remainder does not equal 3
      *           \ multiply by accumulator (cheaper version of "and") 
      r>          \ remove quotient from return stack
      ?dup 0=     \ if quotient does not equal 0, duplicate, else put -1 on stack
     until        \ end loop if top of stack does not equal 0
     *            \ multiply result of both checks (cheaper "and")
   until          \ end outer loop
 ;                \ end word definition

Answer 30

C, 81 bytes

f(int n){int m;l:if(++n%3){for(m=n;m>0;m/=10)if(m%10==3)goto l;return n;}goto l;}

Answer 31

reticular, 30 bytes

in v
?v$>1+d3,qds:3@cQm*
;\$o

Try it online!

Explanation

1: initialization

in v

This converts the input to a number, then goes down (v)

2: loop

?v$>1+d3,qds:3@cQm*
   >                 go right!              [n]
    1+               add 1                  [n+1]
      d3,            duplicate and mod 3    [n+1, (n+1)%3]
         qd          reverse and duplicate  [(n+1)%3, n+1, n+1]
           s         cast to string         [(n+1)%3, n+1, `n+1`]
            :3@c     count numbers of "3"   [(n+1)%3, n+1, `n+1`.count(3)]
                Qm*  negate and rotate      [n+1, continue?]
?v                   terminate if continue
  $                  drop continue

3: final

;\$o
 \$o  drop and output
;     terminate

Answer 32

JavaScript, 35 bytes

f=n=>++n%3&&!(n+"").match(3)?n:f(n)

Try it online!

Answer 33

Batch, 93 bytes

@set/pn=
:l
@set/an+=1,r=n%%3
@if %r%==0 goto l
@if not "%n:3=%"=="%n%" goto l
@echo %n%

Takes input on STDIN.

Answer 34

CJam, 19 bytes

ri{)__3%!\`'3e=e|}g

ONLINE

Explanation:

ri{)__3%!\`'3e=e|}g
r                   Get token
 i                  Convert to integer
  {              }  Block
   )                 Increment
    _                Duplicate
     _               Duplicate
      3              Push 3
       %             Modulo
        !            NOT gate
         \           Swap
          `          String representation
           '3        Push '3'
             e=      Count occurrences
               e|    OR gate
                  g While popped ToS is true

If a less verbose explanation was asked, I would have done this:

ri{)__3%!\`'3e=e|}g
ri                  Get integer
  {              }  Block
   )                 Increment
    __               Triplicate
      3%!            Test non-divisibility with 3
         \           Swap
          `'3e=      Count occurrences of '3' in string repr
               e|    OR gate
                  g While popped ToS is true

Answer 35

Pyth, 19 bytes

JhQW|!%J3/`J\3=hJ;J

Test suite

I am sure I can golf this... it's the same as my CJam answer.

Explanation:

JhQW|!%J3/`J\3=hJ;J
  Q                 Evaluated input
 h                  Increment
J                   Assign J to value
       J            Variable J
        3           Value 3
      %             Modulo
     !              Logical NOT
           J        Variable J
          `         String representation
            \3      Value "3"
         /          Count occurrences
    |               Logical OR
               h    Increment
                J   Variable J
              =     Apply function then assign
                 ;  End statement block
                  J Variable J

Answer 36

Clojure, 73 bytes

(fn c[n](let[m(inc n)](if(or(=(rem m 3)0)(some #(=\3 %)(str m)))(c m)m)))

Recursively loops while n is divisible by 3, or contains a 3 in its string representation. Although I'm using unoptimized recursion, it was able to handle 2999999 as an input, so it should be ok.

Ungolfed

(defn count-without-3 [n]
  (let [m (inc n)]
    (if (or (= (rem m 3) 0)
            (some #(= \3 %) (str m)))
      (count-without-3 m)
      m)))

Answer 37

C#, 49 bytes

int A(int n)=>(++n+"").IndexOf('3')*n%3<0?n:A(n);

Slightly different and shorter than the above c#, using recursion and another trick I came up with to condense the two conditions into one

Answer 38

Japt, 11 bytes

_%3«Zsø3}a°U

Run it online

Answer 39

MathGolf, 10 9 bytes

ö)_3‼╧÷+▲

Try it online!

Explanation

The program loops until it finds a number that is neither divisible by 3 or contains the number 3. ‼ is a new addition to MathGolf, and is newer than this challenge (and this answer). It has been an idea I had in mind for a while, but I finally got everything together to implement it.

ö           start block of length 7
 )          increment
  _         duplicate TOS
   3        push 3
    ‼       apply next two operators separately to the stack
     ╧      pop a, b, a.contains(b)
      ÷     is divisible
       +    pop a, b : push(a+b) (works as a logical OR)
        ▲   do while true with pop

Answer 40

Ruby, 29 bytes

->n{0until"#{n+=n%3}"!~/3/;n}

Try it online!

Answer 41

Perl 6, 39 bytes

{my$a=$_+1;$a++while $a%%3||$a~~/3/;$a}

Answer 42

BotEngine, 770 107x7 = 749 (740 bytes)

This can almost certainly be made rather more compact than it currently is, but I finally managed to get it working at least.

v  0 1 2 3 4 5 6 7 8 9 $ $   0 1 2 3 4 5 6 7 8 9 $  0 1 2 3 4 5 6 7 8 9 $> 0 1 2 3 4 5 6 7 8 9 $v$ $3
I>>S S S S S S S S S S S>S$v>S S S S S S S S S S S >S S S S S S S S S S S >S S S S S S S S S S S>e>SS~v
R  e1e2e3e4e5e6e7e8e9e0e1>e ^e0e1e2e3e4e5e6e7e8e9e$ e0e1e2e3e4e5e6e7e8e9>^ e0e1e2e3e4e5e6e7e8e9>^  Re3  $
$e^                  < e$   ^<     <     <     <        <     <     <        <     <     <         P>  >S~v
>^ >>>>>>>>>>>>>>>>>>>>>^ ~<   >     >     >       ^<     <     <     <        <     <     <      ^   <^  <
                                 >     >     >        >     >     >       ^<     <     <     <          e$
  ^                                              <                                                      <

Input and output is in standard big-endian decimal, although most of the program uses little-endian internally to make the increment cycle more straightforwards.

Answer 43

APL(NARS), 54 chars, 108 bytes

r←h w;c
r←c←0
→3×⍳(0=3∣r)∨'3'∊⍕r⋄c+←1⋄→0×⍳r>w
r+←1⋄→2

I prefer this, the loop, to all recursive functions; test:

  h¨1 2 11 22 29 251    
2 4 14 25 40 254 
  h¨3 6 10   
4 7 11 

Answer 44

Binary-Encoded Golfical, 80 bytes

This binary-encoded format can be converted to the standard graphical version using the encoder utility included in the github repo, or run directly using the interpreter by adding the -x flag.

Hexdump of binary encoding:

01 70 03 15 14 14 1b 1a 14 04 01 14 14 2c 14 14
00 03 14 14 0a 01 14 14 2f 14 14 53 2d 14 23 1d
14 32 14 14 1b 14 1a 00 0a 14 14 0a 01 14 14 2f
14 14 53 31 14 06 03 14 14 23 1d 14 00 0a 14 14
0a 01 1c 14 2d 17 14 3d 2d 14 23 1d 14 1c 2c 1d

Original image (23x3):

Magnified 20x:

Answer 45

TI-BASIC, 36 bytes

Repeat fPart(Ans/3) and max(3≠int(10fPart(Ans₁₀^(seq(-X-1,X,0,log(Ans:Ans+1:End:Ans

Input is in Ans.
Output is in Ans and is implicitly printed when the program completes.

Examples:

17
              17
prgmCDGFF
              19
299
             299
prgmCDGFF
             400

Explantion:
(Newlines added for readability. They do not appear in the source code.)

Repeat                                                      ;loop until...
  fPart(Ans/3)                                              ; the current number is not
                                                            ;  a multiple of 3
  and max(3≠int(10fPart(Ans₁₀^(seq(-X-1,X,0,log(Ans         ; and until it does not
                                                            ;  contain any 3s
Ans+1                                                       ;add 1 to the current number
End
Ans                                                         ;leave the current number
                                                            ; in "Ans" and implicitly
                                                            ; print it

---

Note: TI-BASIC is a tokenized language. Character count does not equal byte count.

Answer 46

C, 59 bytes

n,m;f(){if(++n%3)for(m=n;m;m/=10)(m%10==3)?f():0;else f();}

Answer 47

K (oK), 24 23 bytes

Solution:

(1+)/[{(~3!x)|51in$x};]

Try it online!

Explanation:

Iterate from input+1 until valid number is found. Bit of a cheat dropping whitespace between 51 and in.

(1+)/[{(~3!x)|51in$x};] / the solution
    /[{             };] / iterate (/) while {} is true
                  $x    / string x, e.g. 12 => "12"
              51in      / is "3" (51 in ASCII) in the string?
             |          / or
       (    )           / do this together
         3!x            / x modulo 3
        ~               / not
 1+                     / add 1 to x (e.g. x++)