Palindromic Prime Factors

Question

Palindromic prime problems are pretty common, but that's not what this question is about. In this challenge, the number doesn't have to be a palindrome, its prime factors do.

Task

Your code has to take a single positive integer as input. Then check if any of the permutations of the prime factors of that integer are palindromic when concatenated. If so, output one of them (the list of factors, not the concatenated string). Else, you have to output -1.

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

Test Cases

11 -> [11]
4 -> [2, 2]
39 -> [3, 13]
6 -> -1
1207 -> [17, 71]
393 -> -1
2352 -> [2, 2, 7, 3, 7, 2, 2]

Answer 1

05AB1E, 7 bytes

Òœ.ΔJÂQ

Try it online!

Explanation:

Ò            # prime factorization of the input
 œ           # permutations
  .Δ         # find the first one such that
    J        # concatenated
     ÂQ      # is a palindrome

(.Δ conveniently defaults to -1, so no extra work needed)

Answer 2

Pyth, 14 bytes

-2 bytes by @FryAmTheEggman

h+f_IjkT.pPQ_1

Explanation:

h                 first element of
 +                (append a -1 to the end in case the filter is empty)
  f                 filter by lambda T:
   _I                 is invariant under reversing
     jkT              stringified list
   .p                over permutations of
     P Q             prime factors of Q with duplicates
  _1              -1

Thanks @FryAmTheEggman for reminding me about I. I don't think I've used it before.

Test suite

Answer 3

CJam - 17 bytes

Thanks to Martin Büttner for saving me 10 bytes!

Wqimfe!{s_W%=}=p;

My first time writing in CJam! Explanation:

W              # Push a -1 onto the stack
q               # Get input
i               # Convert to integer
mf              # Find prime factorization
e!              # Find all permutations
{...}=          # Find permutation which...
s               # Convert to string
_               # Copy string
W%              # Get inverse
=               # Check if inverse == original
p;              # Print top of stack and discard the rest

Answer 4

Ruby, 89+7=96 102+7=109

->n{n.prime_division.flat_map{|*a,b|a*b}.permutation.find{|x|x.join==x.join.reverse}||-1}

+7 for the -rprime flag.

Sigh, some Ruby builtins have such long names... at least that makes the code fairly self-explanatory.

The flat_map bit is because prime_division returns ex. [[2, 2], [3, 1]] for input 12 (which represents 2231).

Thanks to @histocrat for 13 bytes!

Answer 5

Julia, 132 122 bytes

n->(x=filter(p->(q=join(p))==reverse(q),permutations(foldl(vcat,[[repeated(k,v)...]for(k,v)=factor(n)]))))==[]?-1:first(x)

This is a lambda function that accepts an integer and returns either an array or -1. To call it, assign it to a variable.

Ungolfed:

function f(n::Int)
    # Construct an array of all prime factors of n
    P = foldl(vcat, [[repeated(k, v)...] for (k, v) in factor(n)])

    # Filter the set of permutations of this array to only
    # those such that the string constructed by concatenating
    # all elements is a palindrome
    x = filter(p -> (q = join(p)) == reverse(q), P)

    # If x is empty, return -1, otherwise get the first array
    # in the collection
    return x == [] ? -1 : first(x)
end

Saved 10 bytes thanks to Glen O!

Answer 6

Brachylog, 10 bytes

ḋp.cX↔X∨_1

Try it online!

  .           The output is
 p            a permutation of
ḋ             the prime factorization of
              the input
   c          such that concatenated
    X         it is the variable X
     ↔        which reversed
      X       is still X;
       ∨      if this is not possible,
              the output is
        _1    -1.

Initially, I had expected that having to output -1 instead of being allowed to fail would be at a fairly large byte cost, but since the output in the case of success can't be concatenated, it only costs the two bytes necessary to write _1 (if we removed those, it would leave the output unconstrained defaulting to 0, and if we additionally changed the ∨ to ∧, the predicate would fail instead), because we need to break unification with the implicit output either way. (If the concatenation was the output for success but -1 was still the output for failure, we'd have ḋpc.↔|∧_1 or ḋpc.↔.∨_1. In the shortest case, where the output is concatenated and the predicate can fail, the whole thing is only five bytes: ḋpc.↔. Although not outputting the actual factors gives it more of a decision-problem feel...)

Answer 7

Haskell, 122 bytes

import Data.Numbers.Primes
import Data.List
f x=head$[p|p<-permutations$primeFactors x,s<-[show=<<p],s==reverse s]++[[-1]]

Usage example: f 39 -> [3,13].

The obvious brute force approach. Iterating over all permutations of the prime factors and check for palindroms. Pick the first one. If there are none, the list is empty and the appended [-1] jumps in.

Answer 8

Perl 6, 100 bytes

{$/=$_;map(->\f{|({$/%f||($//=f)&&f}...^*!==f)},2..$_).permutations.first({.join.flip eq.join})||-1}

{
  # store copy of argument in $/
  $/ = $_;
  # uses $/ so that I don't have to declare a variable

  # find the prime factors
  map(
    ->\f{
      # Slip so that outer list of all prime factors is flat
      |(
        {
          $/ % f    # return modulus
          ||        # or
          ($/ /= f) # factor the prime out of $/
          &&        # and
          f         # return factor
        }
        # produce a list of them and
        # stop when it returns something other than the factor
        # also ignoring the last non-factor value
        ...^ * !== f
      )
    },
    # find the factors out of the values from 2
    # up to the original argument
    2..$_
    # don't need to skip the non-primes as their
    # prime factorization will have already be
    # factored out of $/
  )

  # try all permutations of the prime factors
  .permutations

  # find the first palindromic one
  .first({ .join.flip eq .join })

  # return -1 if .first returned Nil or empty list
  || -1
}

Usage:

# give it a lexical name
my &prime-palindrome = {...}

say prime-palindrome    1; # -1
say prime-palindrome    2; # (2)
say prime-palindrome   11; # (11)
say prime-palindrome   13; # -1
say prime-palindrome   39; # (3 13)
say prime-palindrome   93; # (31 3)
say prime-palindrome    6; # -1
say prime-palindrome 1207; # (17 71)
say prime-palindrome  393; # -1
say prime-palindrome 2352; # (2 2 7 3 7 2 2)
say prime-palindrome 2351; # -1
say prime-palindrome 2350; # -1

---

About half of it (53 bytes) is taken up with the prime factorization code.

$/=$_;map(->\f{|({$/%f||($//=f)&&f}...^*!= f)},2..$_)

If there were a prime-factorize method the whole thing could be significantly shorter.

{.prime-factorize.permutations.first({.join.flip eq.join})||-1} # 63

Answer 9

Jelly, 16 bytes

ÆFŒṙŒ!VŒḂ$ƇḢ¹-¹?

Longer than I expected, both in the byte count and the time it took to write.

Try it online!

Explanation:

ÆFŒṙŒ!VŒḂ$ƇḢ¹-¹?
ÆFŒṙ                Get the prime factors (gets them as exponents then run-length decodes).
    Œ!              Get the permutations.
          Ƈ         Filter (keep) the ones that...
       ŒḂ$          ...are palindromic when...
      V             ...joined.
           Ḣ        Take the first.
              ¹?    If the value is truthy...
            ¹       ...return the value...
             -      else return -1.

Answer 10

Japt -F-1, 9 bytes

k á æ_¬êS

Try it

Answer 11

Japt, 18 bytes

Almost as short as CJam...

Uk á f_¬¥Z¬w} g ªJ

Try it online!

How it works

        // Implicit: U = input, e.g. 2352
Uk      // Factorize the input.      [2,2,2,2,3,7,7]
á       // Take permutations.        [[2,2,2,2,3,7,7],[2,2,2,2,7,3,7],[2,2,2,7,2,3,7],...]
f_   }  // Filter to only the ones that return truthily to this function:
Z¬¥Z¬w  //  Return Z.join('') == Z.join('').reverse().
        //                           [[2,2,7,3,7,2,2],[2,7,2,3,2,7,2],[7,2,2,3,2,2,7]]
g       // Take the first item.      [2,2,7,3,7,2,2]
ªJ      // If falsy, resort to -1.   [2,2,7,3,7,2,2]

Answer 12

JavaScript (ES6), 256 244 208 187 bytes

Saved 36 bytes thanks to @Neil

x=>eval("for(a=[],i=2;x>1;x%i?i++:(a.push(i),x/=i));p=-1,f=(z,t=[])=>z[0]?z.map((u,i)=>f([...z.slice(0,i),...z.slice(i+1)],[...t,u])):(y=t.join``)==[...y].reverse().join``&&(p=t),f(a),p")

Defines an anonymous function; prepend e.g. F= to use it. It's actually quite fast on input of 2352, only taking ~150 milliseconds to finish on my computer.

Answer 13

APL(NARS), 169 chars, 338 bytes

∇r←F w;i;k;a;m;j
  r←⊂,w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m⋄r←r,m,¨∇w[a∼i]⋄j←m
B: i+←1
C: →A×⍳i≤k
∇
G←{F⍵[⍋⍵]}
f←{∨/k←{⍵≡⌽⍵}¨∊¨⍕¨¨v←Gπ⍵:↑k/v⋄¯1}

G would be the function find the permutations and f is the function of this exercise; test:

  ⎕fmt f¨11 4 39 6 1207 393 2352 
┌7───────────────────────────────────────────────────┐
│┌1──┐ ┌2───┐ ┌2────┐    ┌2─────┐    ┌7─────────────┐│
││ 11│ │ 2 2│ │ 3 13│ ¯1 │ 17 71│ ¯1 │ 2 2 7 3 7 2 2││
│└~──┘ └~───┘ └~────┘ ~~ └~─────┘ ~~ └~─────────────┘2
└∊───────────────────────────────────────────────────┘