# Count without 3

### 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.

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 , so the shortest code in bytes wins.

### Test cases

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

• I feel like we had a challenge like this... – Conor O'Brien Nov 3 '16 at 2:06
• It was always 7 that was skipped when I played it, but you'd say something else, instead, rather than going to the next number in line. – mbomb007 Nov 3 '16 at 13:51
• @mbomb007: When I played it, you would not be removed from the circle. Instead, you would drink. But that wasn't in the elementary school. Anyway, getting over 80 was near impossible, especially after the first hour. – tomasz Nov 3 '16 at 21:49
• – Dennis Nov 4 '16 at 14:16
• @mbomb007: That would depend on the proof of whatever you are drinking. – tomasz Nov 4 '16 at 14:16

# 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

• Answers like this are so beautiful in Brachylog :) – Emigna Nov 3 '16 at 13:40
• @Emigna It almost doesn't feel golfy enough sometimes because it basically describes the challenge directly. That's the case for a lot of answers in that language :) – Fatalize Nov 3 '16 at 13:41

# JavaScript (ES6), 30 bytes

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

• Both index 2 and index 3 return the number 4 with this function – nl-x Nov 3 '16 at 16:11
• @nl-x Yes, because 4 is the next number in the sequence after both 2 and 3. It's not indexed; it's simply the next number in the sequence. – ETHproductions Nov 3 '16 at 16:12
• I think I'm starting to understand it... My bad – nl-x Nov 3 '16 at 16:14

# 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 >:.

   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  • Well, J is probably the most smiley-prone programming language. – Adám Dec 12 '16 at 0:24 ## 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]inx:x-=1 print-x  • The two-variable updating looks much too complicated. I think you just need x=input()+1 while'3'[:x%3]inx:x+=1 print x. – xnor Nov 3 '16 at 5:15 • @xnor, oh yeah silly me I don't know why I did that – Daniel Nov 3 '16 at 11:32 • One byte improvement by starting with x=~input(), subtracting instead of adding, and printing -x. – Mitch Schwartz Nov 3 '16 at 14:39 • @Artyer That's only 1 of the 3 mistakes introduced in that edit. – Mitch Schwartz Nov 3 '16 at 19:21 • @Dopapp The current revision (Without the space) is 43 bytes? mothereff.in/… – Artyer Nov 3 '16 at 20:52 # 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  ## 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

• @dan1111 It's Perl, what did you expect? Clarity? – Erik the Outgolfer Nov 4 '16 at 14:46
• @EriktheGolfer what? This is the very definition of "self-documenting code". – user7486 Nov 4 '16 at 14:47
• @dan1111 It seems you know Perl. I have no idea of how Perl works, because of its famous weirdness. – Erik the Outgolfer Nov 4 '16 at 14:50
• @dan1111 Thanks! Quite happy with how short it turned out! – Dom Hastings Nov 4 '16 at 16:58
• @DomHastings Well, in PPCG, we take Perl as the top level of weirdness, and Jelly/Actually/O5AB1E as the top level of mess. It seems that you haven't ever seen this challenge then :) – Erik the Outgolfer Nov 4 '16 at 17:05

# Java 8, 575655 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

• You can use | instead of || – Numberknot Nov 3 '16 at 4:13
• @Numberknot I had no idea bitwise operators functioned as logical ones in some contexts! Thanks! – Socratic Phoenix Nov 3 '16 at 10:43
• Why the do-while? Just a regular for-loop is shorter: i->{for(;++i%3<1|(i+"").contains("3"););return i;} (50 bytes) – Kevin Cruijssen Nov 3 '16 at 11:08
• @KevinCruijssen Well... I thought of comparing while and do-while, and they both gave me the same score, but I liked the way do-while looked... I didn't think of using a for loop... Thanks! – Socratic Phoenix Nov 3 '16 at 11:33

# 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


## 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


# R, 46 bytes

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

• I think that returning a value (rather than printing to stdout) is allowed, so you can save 5 bytes by having just n instead of cat(n). – rturnbull Nov 4 '16 at 14:52

# Python 2, 4944 42 bytes

f=lambda x:'3'[:~x%3]in~xand 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.

• You can do this in Python 2: f=lambda x:f(x+1)if x%3>1or'3'inx+1else-~x. If you want to keep Python 3, you can golf the last x+1 to -~x and remove the space. – Erik the Outgolfer Nov 4 '16 at 14:41
• @EriktheGolfer Thanks! I'll change it to Python 2, as it's way shorter. – 0WJYxW9FMN Nov 4 '16 at 17:28
• 42s: f=lambda x:'3'[:~x%3]in~xand f(x+1)or-~x and f=lambda x:f(x+1)if'3'[:~x%3]in~xelse-~x – Mitch Schwartz Nov 4 '16 at 17:56

# Lua, 58 Bytes

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


## Pyke, 13 bytes

Whii3%!3i{|


Try it here!

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

• At first I though this said while at the beginning. – Conor O'Brien Nov 3 '16 at 18:37
• If you glance at it I can see that – Blue Nov 3 '16 at 18:38

# C#, 56, 51 bytes.

This is surprisingly short for a C# answer!

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

• You can get it down to 43 if you make it recursive t=x=>(++x)%3<1|(x+"").Contains("3")?t(x):x; In Visual Studio, you just need to define the variable and set it to null Func<int, int> t = null; and then define the recursive function on the following line. – Grax32 Nov 3 '16 at 17:17
• The problem is that if I make it recursive, I then have to count the function and type definitions. – Morgan Thrapp Nov 3 '16 at 17:19
• Is there somewhere I can go to see these guidelines? I find C# golfing confusing on here. – Grax32 Nov 3 '16 at 17:21
• @Grax Basically, you need to include any code required for the code to run except the assignment to a name in the case of a non-recursive function. I don't know where you would find a concrete set of guidelines, unfortunately. – Morgan Thrapp Nov 3 '16 at 17:24
• @MorganThrapp please check out my c# answer with recursion at 49 bytes :) – lee Mar 2 '18 at 6:26

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  • Also 50 bytes: until(\x->mod x 3>0&&notElem '3'(show x))succ.succ. – nimi Nov 3 '16 at 13:51 # Pyth, 11 bytes f&-IT3%T3h  Try it online: Demonstration or Test Suite ### Explanation: f&-IT3%T3hQ implicit Q at the end f hQ find the smallest integer T >= input + 1 which fulfills: -IT3 T is invariant under removing the digit 3 & and %T3 T mod 3 leaves a positive remainder  ## GolfSharp, 43 bytes m=>r(m,m).w(n=>n%3>0&!n.t().I("3")).a()[1];  # 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. • you can use i instead of "#{i}" – Mohammad Nov 5 '16 at 7:21 # 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  # 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. # PHP, 605554 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. • You can save 7 bytes by just using a program taking input from the command line rather than a function: for($i=$argv[1];!(++$i%3)|strpos(" $i",'3'););echo$i; it may be possible to do better by assigning $i while using it too. – user59178 Nov 3 '16 at 16:39 • @user59178 I assumed the function had to return$i – Xanderhall Nov 3 '16 at 19:14
• most of the time questions are pretty flexible in how input and output is done, as long as the right thing is given and received. Besides, looking at answers in other languages, most choose to print to stdout. – user59178 Nov 4 '16 at 9:03
• Save a byte with strpos(_.$i,'3') – Alex Howansky Nov 4 '16 at 18:12 • Save one byte with %3<1, one with 51 instead of '3', two more with strstr($i) instead of strpos(_.$i) and another two by swapping the | operands in the second version: <?for(;strstr($i=++$argv[1],51)|$i%3<1;);echo$i; -> 48 bytes – Titus Dec 6 '16 at 16:15 # 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.

# APL (Dyalog Unicode), 332827 19 bytesSBCS

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 bytesSBCS

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


# 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


# 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;}


# 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


## 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.

# 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


# 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

• I posted a way shorter solution. Nevertheless here is a tip for your approach: Don't use the variable J. You can increment Q. And if your doing it clever, you can inline the operation into the while condition: W|!%=hQ3/Q\3;Q. – Jakube Nov 8 '16 at 19:01
• Sorry: W|!%=hQ3/Q\3;Q – Jakube Nov 8 '16 at 19:07
• @Jakube The variable is not just incrementing but thanks. – Erik the Outgolfer Nov 9 '16 at 11:44

## 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)))
`