Very interesting background

Comcoins are a currency like any other. The residents of Multibaseania (an economically robust system of city-states with very few residents in a galaxy far, far away) use Comcoins to conduct transactions between themselves. Comcoins are represented by unique codes on special not-paper slips, and when you pay you give the vendor your slip.

However, just like any currency, there are those villainous types that try to take advantage of the system and inflate the currency because they are bored.

To combat this unquestionably illegal behavior, the Multibaseanian governments came together and devised a way to prove that the money is legitimate. The top idea from the think tank was: whenever a Comcoin is given to a vendor, the vendor runs a program that checks if it is legitimate. How does one know if a Comcoin is legitimate?

A legitimate Comcoin is one where:

When the Comcoin's unique code is converted into the bases 2-10, inclusive, that number is composite (i.e. not prime). Also, all of the unique code's digits in base 10 are either 1 or 0, and its length in base 10 is between 1 and 5 inclusive.

Very important example: in base 5, 111 is 421. Even though 111 is not prime, 421 is, so the Comcoin is invalid.

The challenge

Write a function or program that takes a Comcoin's code (a number), which is in base 10 and is an integer. Then, print or return a truthy or falsy value depending on whether that Comcoin is legitimate (criteria above), respectively.

I/O examples

Input     Output

101         False // because it is prime in base 2
1010        True
10101       True
1010111     False // because it is longer than 5 digits
123         False // because it does not contain *only* 0's and 1's
10111       False // because it is prime in base 6

This is code golf, so shortest code in bytes wins!


A Comcoin is not a number that is not prime, but is a number that is composite.

Inspiration from qualification round of Google CodeJam 2016.

  • 4
    \$\begingroup\$ Related... \$\endgroup\$
    – Doorknob
    Apr 11 '16 at 1:43
  • 11
    \$\begingroup\$ What's with all the primality testing and base conversion? I know this was inspired by a Google code jam question, but I feel like these topics have been way overdone on PPCG. And my comments from here also apply. \$\endgroup\$
    – xnor
    Apr 11 '16 at 1:51
  • 6
    \$\begingroup\$ What about an input of 1? It's not composite in any base, nor is it prime. Is it a legitimate Comcoin? \$\endgroup\$
    – Value Ink
    Apr 11 '16 at 5:38
  • 5
    \$\begingroup\$ "When the Comcoin's unique code is converted into the bases 2-10, inclusive, that number is composite" makes no sense. The divisibility properties of a number are independent of the way the number is represented. \$\endgroup\$ Apr 11 '16 at 9:36
  • 4
    \$\begingroup\$ Well you definitely solved the inflation problem if you can only ever mint 18 comcoins... \$\endgroup\$ Apr 11 '16 at 15:42

11 Answers 11


Python 2, 62 56 49 bytes

lambda n:max(`n`)<"2"and 0x5d75d750>>int(`n`,2)&1

Credit to @Sp3000 for the max trick to ensure binary digits.

  • \$\begingroup\$ A black magic hardcode of all relevant primes? Nice, how does it work? \$\endgroup\$
    – Value Ink
    Apr 11 '16 at 6:40
  • \$\begingroup\$ @KevinLau It's function should be apparent once you realize how many 5-digit binary numbers there are :) \$\endgroup\$
    – orlp
    Apr 11 '16 at 6:41
  • \$\begingroup\$ You left out 1111. \$\endgroup\$
    – xsot
    Apr 11 '16 at 8:21
  • \$\begingroup\$ @xsot Fixed, had a little bug in my generation script. \$\endgroup\$
    – orlp
    Apr 11 '16 at 13:36
  • \$\begingroup\$ wow... that's clever. \$\endgroup\$
    – cat
    Apr 11 '16 at 13:48

JavaScript (ES6), 38 27 bytes


Port of @orlp's Python answer, except that JavaScript's precedence and weak typing allows me to shift the integer even if it's not valid in base 2, and then bitwise and it with the boolean. Returns 0 or 1 as appropriate. Note that I'm not using @orlp's constant any more, instead I'm assuming the following list of comcoins is valid:


Edit: Fixed to check the length of the comcoin, since JavaScript's shift operator works modulo 32.


MATL, 20 bytes


Input is a string.

Try it online!


n6<    % take input implicitly. Is length less than 6?
G50<   % push input again. Array that contains true for digits less than 2
9:Q    % push array of bases: [2,3,...,10]
"      % for each
  G    %   push input again
  @    %   push current base
  ZA   %   interpret input as if it were in that base, and convert to decimal
  Zp~  %   true for composite numbers
  v    %   concatenate vertically all results up to now
  A    %   true if all results were
       % end for each implicitly
       % display implicitly

Julia, 83 81 bytes


This is a function that accepts an integer and returns a boolean. It's a straightforward check on the conditions of being a Comcoin:

  • Length as a string between 1 and 5 inclusive: endof(s)<6
  • All zeros and ones: all(c->c∈"01",s)
  • No primes in any base from 2 to 10: !any(b->isprime(parse(Int,s,b)),2:10)

Saved 2 bytes thanks to Luis Mendo!


JavaScript (ES6), 37

This should work better than the current ES6 answer Now the other ES6 answer is clearly better

Edit 0 and 1 not valid, the magic number changes


Test (see below to see how the magic number is built)



function test() {
  var x=+I.value
  console.log(x+' '+F(x))


// How the mask is built

  if(x<=2)return x==2
  if(x%2==0)return false
  var i,q=Math.sqrt(x)
    if(x%i==0)return false
  return true;

  var n,m,i,p,mask=''
      p=m<2 || isPrime(m)
    if(!p) console.log('Y',i,n)
  console.log(mask, parseInt(mask,2))
  // result
  // 0001010101110101010111010111001,180006585}
<input value='11111' type='number' id=I oninput='test()'><pre id=O></pre>


Mathematica, 97 bytes


Hey, at least I tried...

#<1*^5&&                                                                                          less than 100000?
        Tr@DigitCount[#][[2;;-2]]<1&&                                                             no digits 2-9?
                                     FromDigits@IntegerDigits[#,a+1]~Table~{a,9}~NoneTrue~PrimeQ& composite in all bases?

Ruby, 81 80 74 bytes

Anonymous function, takes input as a string and returns true or a falsy value (false if it fails a prime check, nil if it contains characters that aren't 0 or 1)

Uses some regex magic suggested by @QPaysTaxes, which thankfully works (within reasonable time) because of the promise that the coin signature has max 5 characters. Also, I forgot to actually check for the length, so only 1 byte was saved overall.

Since 0 and 1 aren't composite numbers in any base, I could save more bytes by modifying my regex.


Old version using Ruby's built-in prime checker. 85 bytes after properly checking for length.

->n{require'prime';n=~/^[01]{1,5}$/&&(2..10).map{|b|Prime.prime? n.to_i(b)}&[!p]==[]}
  • \$\begingroup\$ As a side note, you can check primality in fewer bytes with this dark magic: '1'*n.to_i(b) !~/^1?$|^(11+?)\1+$/. Or at least I think you can. To be honest, I have no idea how that works, so it might not. \$\endgroup\$
    – Nic
    Apr 11 '16 at 2:17
  • \$\begingroup\$ Oh! A regex pattern for composite numbers, and a check to make sure it doesn't match. Yeah, that'll work. (The black magic works by turning the number into a string of 1s and uses regex groups to find a pair of numbers that will multiply and fit the pattern.) \$\endgroup\$
    – Value Ink
    Apr 11 '16 at 5:47

05AB1E, 18 17 bytes


-1 byte and bug-fix thanks to @Grimmy.

Outputs 1/0 for truthy/falsey respectively.

Try it online or verify all test cases or verify the first 40 binary numbers and 100 regular numbers.

(Now longer) 18 bytes alternative:


Outputs 1 for truthy and a non-1 integer for falsey (note: only 1 is truthy in 05AB1E, so this is allowed according to the meta).

Try it online or verify all test cases or verify the first 40 binary numbers and 100 regular numbers.

Both programs also works for edge-case 1, unlike some other answers.


Θ       # Check if the (implicit) input is exactly 1 (1 if 1; 0 otherwise)
Ig      # Push the input again, and pop and push its length
  5›    # Check if this length is larger than 5 (1 if length>5; 0 if length<=5)
I       # Push the input again
 TL     # Push a list in the range [1,10]
   B    # Convert the input to each of those bases
    p   # Check for each whether it is a prime (1 if prime; 0 if not)
     à  # Pop and push the maximum to check if any are a prime
I       # Push the input yet again
 1K     # Remove all 1s
   `    # And push all remaining digits separated to the stack
O       # Sum all values on the stack
 _      # And check whether it is exactly 0 (1/truthy if 0; 0/falsey if >0)
        # (after which this result is output implicitly)

46b     # Push 46 as binary: 101110
   IC   # Push the input, and convert it from binary to an integer
        # (NOTE: unfortunately also works for non-binary inputs, so we'll fix those later)
     è  # Use that to index into the 101110 (0-based and with wraparound)
Iт@     # Push the input again, and check that it's >= 10
Ig6‹    # Push the input again, and check that its length is < 6
P       # Take the product of all values on the stack
 I      # Push the input again
  Tм    # Remove all 1s and 0s
    +   # And add any remaining digits to the product
        # (after which the result is output implicitly)

Python, 161 152 bytes

Sigh. Assign the lambda to use it.

def p(n):
 while i>2:i-=1;a*=n%i
 return a>1
lambda s:all([all(map(lambda i:not p(int(s,i)),range(2,11))),filter(lambda i:i in"01",s)),len(s)<6])

Factor, 128 bytes

[ dup [| a | 2 10 [a,b] [ a swap base> prime? not ] all? ] swap [ [ [ 49 = ] [ 48 = ] bi or ] all? ] [ length 6 < ] bi and and ]

I'll try to golf this more in a sec.

Well, here's the less golfed version I thought might be shorter, but it's 133 bytes...

[ [ [let :> a 2 10 [a,b] [ a swap base> prime? not ] all? ] ] [ [ [ [ 49 = ] [ 48 = ] bi or ] all? ] [ length 6 < ] bi ] bi and and ]

Actually ungolfed:

: comcoin? ( a -- t/f ) 
    [let :> a
      2 10 [a,b] [ a swap base> prime? not ] all? 
  ] [ 
    [ [ [ 49 = ] [ 48 = ] bi or ] all? ] 
    [ length 6 < ] bi 
  ] bi 
  and and ;

Python 3, 222 bytes

I wanted to try to do the naive method purely functionally, without looping. Here it is.

(lambda A:all([F(A)for F in[lambda r:all(map(lambda s:not(lambda i,b:lambda n:list(filter(lambda i:not n%i,range(2,n)))(int(i,b))(r,s),range(2,11))),lambda r:0!= len(filter(lambda d:d not in"01",r)),lambda r:0<len(r)<6]]))


(lambda A:
        [F(A) for F in [
            lambda r: all(
                    lambda s:
                            lambda i, b:
                                lambda n:
                                        lambda i: not n % i, range(2, n)))
                            )(int(i, b))(r, s),
                            range(2, 11))),
            lambda r: 0 != len(filter(lambda d: d not in "01", r)),
            lambda r: 0 < len(r) < 6

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.