# Palindromic Prime Factors

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.

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 , 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]
``````
-
Can other distinguishable values than `-1` be returned? In Perl 6 I'm thinking about `Nil`,`Fail` or other undefined values. Also can the output be any Positional value? – Brad Gilbert b2gills Jan 18 at 4:45
List, Array, Seq, Range, Buf, Slip are all Positional values. That is they do the Positional Role. – Brad Gilbert b2gills Jan 18 at 5:01

# 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

-
`jk` is the same as `s`M` – Maltysen Jan 18 at 4:14

# 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
``````
-
You can reverse a string (or array) with `W%`. You can also use `=` with a block to get the first palindromic prime factorisation. That makes for 18 bytes: `Wrimfe!{s_W%=}=p];` ... you can save one more by terminating with an error (since the error output goes to STDERR): `Wrimfe!{s_W%=}=p;` – Martin Ender Jan 18 at 8:22
@MartinBüttner This is why I love PPCG. Everyone is so helpful and friendly! – KoreanwGlasses Jan 18 at 14:15

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

-
At a glance, I see a few ways to improve this (just based on basic golfing). Use `foldl` rather than `reduce` (they do the same thing, but `foldl` has defined order and is one byte shorter). Use a direct comparison with an empty structure instead of `isempty` (I'm not 100% sure what type `x` is, but if it's a set, for instance, use `x==[]`). And use `(q=join(p))` and then just `q` in the filter to save two more bytes. – Glen O Jan 18 at 16:36
Also, I could be mistaken, but if `x` is an array, then rather than `first(x)`, just use `x[]`. – Glen O Jan 18 at 16:40
@GlenO Thanks so much as always! I had initially tried `==[]` and it was giving me errors but I tried again now and it's working. I must have messed something up before. ¯\_(ツ)_/¯ The only suggestion I couldn't use is getting rid of `first`; in this case I have to use `first` because `x` is an iterator/collection/something that doesn't have `getindex` defined. – Alex A. Jan 18 at 19:56

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

-
@histocrat That was a mistake on OP's part (see comments on the question). Thanks, that's a neat trick with the splat. – Doorknob Jan 18 at 4:31

``````import Data.Numbers.Primes
import Data.List
``````

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.

-

# 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]
``````
-

# JavaScript (ES6), 256244208 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.

-
I don't know about faster but definitely shorter: `x=>eval("for(a=[],i=2;x>1;x%i?i++:(a.push(i),x/=i));p=[],f=(z,t=[])=>z.length?z‌​.map((u,i)=>f([...z.slice(0,i),...z.slice(i+1)],[...t,u])):(y=t.join``)==[...y]‌​.reverse().join``&&p.push(t),f(a),p[0]||-1")` – Neil Jan 19 at 22:26
@Neil Thanks, that also happens to be a few times faster than my algorithm! – ETHproductions Jan 21 at 13:28
36 bytes? I think that must be a record for me. – Neil Jan 21 at 21:17

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