3
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Related... \$\endgroup\$ – Doorknob Apr 11 '16 at 1:43
  • 9
    \$\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
  • 4
    \$\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
  • 4
    \$\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\$ – Peter Taylor Apr 11 '16 at 9:36
  • 4
    \$\begingroup\$ Well you definitely solved the inflation problem if you can only ever mint 18 comcoins... \$\endgroup\$ – 2012rcampion Apr 11 '16 at 15:42

10 Answers 10

2
\$\begingroup\$

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
\$\endgroup\$
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Julia, 83 81 bytes

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!

\$\endgroup\$
2
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

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?
\$\endgroup\$
1
\$\begingroup\$

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.

->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]==[]}
\$\endgroup\$
  • \$\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 Hartley 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
0
\$\begingroup\$

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])
\$\endgroup\$
0
\$\begingroup\$

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 ;
\$\endgroup\$
0
\$\begingroup\$

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
            ]
        ]
    )
)
\$\endgroup\$

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.