# Is it really a comcoin?

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

## Edit

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.

• Related...
– Doorknob
Apr 11 '16 at 1:43
• 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.
– xnor
Apr 11 '16 at 1:51
• What about an input of 1? It's not composite in any base, nor is it prime. Is it a legitimate Comcoin? Apr 11 '16 at 5:38
• "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. Apr 11 '16 at 9:36
• Well you definitely solved the inflation problem if you can only ever mint 18 comcoins... Apr 11 '16 at 15:42

# Python 2, 6256 49 bytes

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


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

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

## JavaScript (ES6), 38 27 bytes

n=>2641714512>>'0b'+n&n<1e5


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:

100
110
1000
1010
1011
1100
1110
10000
10010
10100
10101
10110
11000
11010
11011
11100
11111

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

# MATL, 20 bytes

n6<G50<9:Q"G@ZAZp~vA


Input is a string.

Try it online!

### Explanation

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


f(x,s="$x")=endof(s)<6&&all(c->c∈"01",s)&&!any(b->isprime(parse(Int,s,b)),2:10)  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 n=>180006585..toString(2)['0b'+n-4]|0  Test (see below to see how the magic number is built) F=n=>180006585..toString(2)['0b'+n-4]|0 console.log=(...x)=>O.textContent+=x+'\n' function test() { var x=+I.value console.log(x+' '+F(x)) } test() // How the mask is built isPrime=x=>{ if(x<=2)return x==2 if(x%2==0)return false var i,q=Math.sqrt(x) for(i=3;i<=q;i+=2) if(x%i==0)return false return true; } buildMask=_=>{ var n,m,i,p,mask='' for(i=1;i<32;i++) { n=+i.toString(2) for(p=0,b=10;b>1;--b) { m=+n.toString(b) p=m<2 || isPrime(m) if(p) { console.log('N',i,n,m,b) break; } } mask+=p?0:1 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 #<1*^5&&Tr@DigitCount[#][[2;;-2]]<1&&FromDigits@IntegerDigits[#,a+1]~Table~{a,9}~NoneTrue~PrimeQ&  Hey, at least I tried... #<1*^5&&Tr@DigitCount[#][[2;;-2]]<1&&FromDigits@IntegerDigits[#,a+1]~Table~{a,9}~NoneTrue~PrimeQ& #<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, 8180 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. ->n{n=~/^[01]{2,5}$/&&(2..10).map{|b|?1*n.to_i(b)=~/^(..+?)\1+$/}&[p]==[]}  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]==[]}

• 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.
– Nic
Apr 11 '16 at 2:17
• 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.) Apr 11 '16 at 5:47

# 05AB1E, 18 17 bytes

ΘIg5›ITLBpàI1KO_


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

Outputs 1/0 for truthy/falsey respectively.

(Now longer) 18 bytes alternative:

46bICèIт@Ig6‹PITм+


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

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

Explanation:

Θ       # 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):
i=a=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]]))


Ungolfed:

(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
]
]
)
)