45
\$\begingroup\$

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

Test cases

  1 ->   2
  2 ->   4
 11 ->  14
 22 ->  25
 29 ->  40
251 -> 254
\$\endgroup\$
  • 5
    \$\begingroup\$ I feel like we had a challenge like this... \$\endgroup\$ – Conor O'Brien Nov 3 '16 at 2:06
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – mbomb007 Nov 3 '16 at 13:51
  • 12
    \$\begingroup\$ @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. \$\endgroup\$ – tomasz Nov 3 '16 at 21:49
  • 10
    \$\begingroup\$ @mbomb007 Depends on the blood alcohol concentration. \$\endgroup\$ – Dennis Nov 4 '16 at 14:16
  • 4
    \$\begingroup\$ @mbomb007: That would depend on the proof of whatever you are drinking. \$\endgroup\$ – tomasz Nov 4 '16 at 14:16

47 Answers 47

1
2
1
\$\begingroup\$

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.)
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 51 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

JavaScript, 35 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
  • 4
    \$\begingroup\$ I am not an expert in JavaScript but this doesn't look very golfed. It looks like you have a lot of whitespace that could be removed. You might want to check out the tips page for JavaScipt. \$\endgroup\$ – Ad Hoc Garf Hunter Nov 3 '16 at 20:29
  • \$\begingroup\$ Ah, sorry, First time on this stackexchange. I thought this was just a problem to solve. Didn't realize there were rules. I wasn't sure what "golfed" meant. \$\endgroup\$ – Oliver Nov 3 '16 at 20:31
  • 4
    \$\begingroup\$ No need to apologize. All puzzles here have a "winning criterion", quite often, such as in this challenge, it is code golf. If you want more general puzzles look into the programming-puzzle tag. Welcome to PPCG I hope you have fun. \$\endgroup\$ – Ad Hoc Garf Hunter Nov 3 '16 at 20:36
  • \$\begingroup\$ "Golfed" means you try to make the program as small as possible. Then you compete against other users to get the shortest Javascript answer. I would read through this page and edit your post if you can come up with a shorter solution. \$\endgroup\$ – James Nov 3 '16 at 21:26
1
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Can you explain this answer? \$\endgroup\$ – sintax Mar 21 '19 at 15:51
  • \$\begingroup\$ @sintax Added some explanatory comments at the provided link. \$\endgroup\$ – SuperJedi224 Mar 23 '19 at 2:12
1
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Japt, 11 bytes

_%3«Zsø3}a°U

Run it online

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Ruby, 29 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 39 bytes

{my$a=$_+1;$a++while $a%%3||$a~~/3/;$a}
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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):

enter image description here

Magnified 20x:

enter image description here

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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 
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

C, 59 bytes

n,m;f(){if(++n%3)for(m=n;m;m/=10)(m%10==3)?f():0;else f();}
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! Which compiler did you use to test this? I can't seem to get it working with gcc, tcc, or clang. Also, functions are required to take input using one of these method. \$\endgroup\$ – Dennis Apr 14 '19 at 1:24
0
\$\begingroup\$

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++)
|improve this answer|||||
\$\endgroup\$
1
2

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.