# 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? Commented Jan 18, 2016 at 4:45
• List, Array, Seq, Range, Buf, Slip are all Positional values. That is they do the Positional Role. Commented Jan 18, 2016 at 5:01
• So.. should we output an empty list for 1, or -1?
– Jo King
Commented Apr 10, 2019 at 7:30
• -1 as element is different to one array that contain only -1
– user58988
Commented May 10, 2019 at 9:41

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

# 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 sM Commented Jan 18, 2016 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; Commented Jan 18, 2016 at 8:22
• @MartinBüttner This is why I love PPCG. Everyone is so helpful and friendly! Commented Jan 18, 2016 at 14:15

## 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. Commented Jan 18, 2016 at 4:31

# 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. Commented Jan 18, 2016 at 16:36
• Also, I could be mistaken, but if x is an array, then rather than first(x), just use x[]. Commented Jan 18, 2016 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. Commented Jan 18, 2016 at 19:56

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

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.

# 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  • A shorter prime factor code section could be $!=$_;({+$!/($!/=1+(2...$!%%*))}...{2>$!}) – Jo King Commented Apr 10, 2019 at 13:06 # 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.


# Japt-F-1, 9 bytes

k á æ_¬êS


Try it

– user58988
Commented May 10, 2019 at 12:31
• @RosLuP The interpreter is still fairly new. I'll ping Shaggy, the creator. Here's a TIO link Commented May 10, 2019 at 13:24
• @RosLuP, what browser are you using? Commented May 10, 2019 at 16:17
• Internet Explorer for Windows Phone 8.1: (cellphone) something that is disappearing , possibly it is better I use my brand new phone android or the browser of windows 10 (Edge it seems they call)
– user58988
Commented May 11, 2019 at 15:33

# 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
Commented Jan 19, 2016 at 22:26
• @Neil Thanks, that also happens to be a few times faster than my algorithm! Commented Jan 21, 2016 at 13:28
• 36 bytes? I think that must be a record for me.
– Neil
Commented Jan 21, 2016 at 21:17

# 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
└∊───────────────────────────────────────────────────┘

`