Palindromic Powers

Question

Powers

We define an important power as a number that can be represented as \$ x^y \$ where \$ x ≥ 2 \$ and \$ y ≥ 2 \$.

Palindrome

We define an important palindrome as a number that is the same written forwards and backward, and is greater than 10. Thus, the last digit must not be 0.

Palindromic Power

We define a Palindromic Power as a number that is both an important palindrome and important power.

Example

My reputation when I first drafted this question was 343, which was an important power as \$ 343 = 7^3 \$. It is also an important palindrome. Thus it is a palindromic power. (Interestingly, the number of badges I have when I first drafted this question was 7).

Your Challenge

Given an integer \$ n \$, print all palindromic powers that are less than (and not equal to) \$ n \$.

Example Program

Your program should produce the same output as this program. The exact order of your answer does not matter

from math import log def is_power(n, base): return not n%base and is_power(int(n//base), base) def is_important_power(n): for base in range(2, int(n**0.5) + 1): if is_power(n, base): return True return False def is_important_palindrome(n): s = str(n) return s == s[::-1] and n>10 def is_palindromic_power(n): return is_important_power(n) and is_important_palindrome(n) def main(number): final = [] for i in range(1, number): if is_palindromic_power(i): final.append(i) return final

These are the palindromic powers under 1000000:

121 343 484 676 1331 10201 12321 14641 40804 44944 69696 94249 698896

Input

You may assume the input is under 100000000.

Scoring

This is code-golf.

Your example program is prone to floating point errors, due to the log and the is_integer check — caird coinheringaahing
– caird coinheringaahing ♦, Commented May 12, 2022 at 0:46
I think there is a way around this, I will change the code later. — Sunny
– Sunny, Commented May 12, 2022 at 0:53
Given that it's such a short list, I could see hard-coding it as a serious possibility. Would certainly have better time complexity than any solution which calculates them from scratch, but this is Code Golf, we don't usually give out points for runtime efficiency... — Darrel Hoffman
– Darrel Hoffman, Commented May 13, 2022 at 14:51

Aiden Chow · Accepted Answer · 2022-05-13 05:40:07Z

Desmos, 177 175 bytes

T->min(T+1,n),o->L[L>9] n=\ans_0 T=0 k=10^{[floor(log(T+0^T))...0]} L=join(o,[T][[0^{n-T}+∏_{A=2}^{T-1}sign(mod(log_AT,1))]=-sign(total(k[1]/kmod(floor(T/k),10))-T)^2]) o=[]

This was really fun to puzzle out and solve in Desmos! Surprisingly, the part to check for an important palindrome is longer than the part to check for an important power.

Might be prone to floating point errors because of the usage of log, but any attempt to fix this will most likely cost more bytes, so I will just leave it like this for now.

Output is shown in the o variable. More info on I/O in the graph links below.

Try It On Desmos!

Try It On Desmos! - Prettified

naffetS · Accepted Answer · 2022-05-12 15:55:57Z

05AB1E, 11 bytes

<TŸʒÓ¿≠yÂQ&

Try it online!

Before Kevin wakes up and outgolfs me. Port of Jelly.

How?

<TŸʒÓ¿≠yÂQ& < # Decrement (implicit) input T # Push 10 Ÿ # Pop top two values of the stack and push inclusive range ʒ # Filter keep for n: Ó # Get the exponents of the prime factorization of n ¿≠ # Is the GCD of the exponents not one?... & # ...and... yÂQ # Is y a palindrome?

Haha. I'm awake now, but I don't see any way to shorten your port. ;) +1 from me. — Kevin Cruijssen
– Kevin Cruijssen, Commented May 12, 2022 at 6:32

caird coinheringaahing · Accepted Answer · 2022-05-13 16:59:06Z

Jelly, 13 bytes

’⁵rŒḂƇÆEg/’ƊƇ

Try it online!

-1 byte thanks to Jonathan Allan!

In order for some \$k = p_1^{e_1}p_2^{e_2}\cdots p_i^{e_i}\$ to be a perfect power (for primes \$p_1, p_2, \dots\$), we must have that \$\gcd(e_1, e_2, \dots, e_i) > 1\$.

How it works

’⁵rŒḂƇÆEg/’ƊƇ - Main link. Takes n on the left ’ - Decrement ⁵r - Range from 10 to n-1 Ƈ - Keep those that are: ŒḂ - Palindromic ƊƇ - Keep those that are non-zero after: ÆE - Prime exponents g/ - Reduce by GCD ’ - Decremented

@JonathanAllan Nice one, I always forget the double filter trick — caird coinheringaahing
– caird coinheringaahing ♦, Commented May 13, 2022 at 12:35

chunes · Accepted Answer · 2022-05-12 03:20:36Z

Factor + `math.primes.factors project-euler.common`, 101 102 bytes

[ iota 10 short tail [ palindrome? ] filter [ group-factors values 0 [ gcd nip ] reduce 1 > ] filter ]

Try it online!

This is a port of caird's Jelly answer. I toyed with some brute force solutions but they came out a little longer.

iota 10 short tail Shortest way (I think) to create an exclusive range from 10 to the input that is empty if the input is less than 11.
[ palindrome? ] filter Get the palindromes within the range.
[ ... ] filter Get the perfect powers within the palindromes.
group-factors values Get the exponents of the prime factorization.
0 [ gcd nip ] reduce Take the GCD of a sequence.
1 > Is it greater than 1?

Note that [ ... ] filter [ ... ] filter is shorter than any kind of boolean and logic that's possible in Factor, as far as I know. Compare these simple examples:

[ odd? ] filter [ 10 > ] filter
[ dup odd? swap 10 > and ] filter
[| n | n odd? n 10 > and ] filter
[ { [ odd? ] [ 10 > ] } && ] filter (short-circuiting [starts to win out at 3-4 conditions])

att · Accepted Answer · 2022-05-12 05:08:44Z

Wolfram Language (Mathematica), 60 bytes

Select[h=Range[#-1],(h[[a#]]=a=h[[#]])<#>9&&PalindromeQ@#&]&

Try it online!

Select[ Range[#-1], ] pick numbers in the range where: h= (h[[a#]]=a=h[[#]]) (if x=a^b, h[[x]]=a) <# an important power #>9&&PalindromeQ@# and an important palindrome

naffetS · Accepted Answer · 2022-05-12 01:55:29Z

Vyxal, 14 bytes

‹₀ṡ'ǐĠvLġċnḂ=∧

Try it Online!

Port of Jelly answer.

How?

‹₀ṡ'ǐĠvLġċnḂ=∧ ‹₀ṡ # Descending range [input - 1, 10] ' # Filter for n: ǐ # Get the prime factorization of n Ġ # Group consecutive identical items vL # Get the length of each ġċ # Is the GCD of this array not one?... ∧ # ...and... nḂ= # Is n palindromic?

ǐĠvL can now just be ∆ǐ in a newer version, but this challenge inspired the builtin. — naffetS
– naffetS, Commented Aug 18, 2022 at 1:07

dingledooper · Accepted Answer · 2022-05-12 04:13:38Z

C (gcc), 117 bytes

Brute force at its finest. It might be improvable by merging the two for loops into one, but I currently have no idea how to go about that.

x,p,i,s,t;f(n){for(x=p=i=10;t=i%n;p=p<i?p*x:x/i||i==s&i/p&&printf("%d\n",i)?++i,x=2:++x)for(s=0;t;t/=10)s=s*10+t%10;}

Try it online!

Ungolfed

x, p, i, s, t; f(n) { for ( x = p = i = 10; i < n; ) { // This loop calculates and sets `s` to the reverse of `i` for (s = 0, t = i; t; t /= 10) s = s * 10 + t % 10; // `p` is a running variable that holds the current // power depending on the base, `x`. if (p < i) { // While `p` is less than `i`, multiply it by `x` // (in other words, increment its exponent) p *= x; } else { if (x >= i) { // If no solution is found, // reset everything and increment `i` p = x = 2, ++i; } else if (i == s && i == p) { // If a solution is found, // print `i`, then reset everything and increment `i` printf("%d\n", i); p = x = 2, ++i; } else { // Otherwise, increment `x` to check for a solution // with the next base p = ++x; } } } }

Laikoni · Accepted Answer · 2022-05-12 15:36:07Z

Haskell, 76 72 64 bytes

f n=[z|x<-[2..n],z<-map(x^)[2..n],z<n,(==)=<<reverse$show z,z>9]

Attempt This Online! Given the ranges [2..n] are used, this aproach is rather inefficient. The ATO Link works for n=1000, but times out for n=10000.

Explanation:

f n = -- function f takes input n [z| -- returns list of all z where ... x<-[2..n], -- ... z = x^y for x in [2..n] z<-map(x^)[2..n], -- and y in [2..n] z<n, -- ... z is smaller than n (==)=<<reverse$show z, -- ... z is an palindrome z>9] -- ... and z is larger than 9

att · Accepted Answer · 2022-05-12 22:33:58Z

C (gcc), 111 bytes

i,t,r;g(n){r=9/--n||g(n);for(t=n;t;t/=10)r=r*10+t%10;for(t=i=2;r==n&i<n;)t=t/n?t-n?++i:printf("%d\n",i=n):t*i;}

Try it online!

Neil · Accepted Answer · 2022-05-12 07:42:55Z

Retina 0.8.2, 100 bytes

.+ $*¶ $.` 10A` G`^(?=(.)+)(?<-1>\1)+$ .+ $* Gr`(?=((?=((1*)(?=\5\3+$)1)(\2*$))\4){2,}1$)^(..+) %`1

Try it online! Link uses n=500 as otherwise it would be too slow. Explanation: Based on my answer to Perfect radicals.

.+ $*¶ $.`

List all the integers up to n.

10A`

Delete the first 10 (i.e. 0..9).

G`^(?=(.)+)(?<-1>\1)+$

Keep only palindromes.

.+ $*

Convert to unary.

Gr`(?=((?=((1*)(?=\5\3+$)1)(\2*$))\4){2,}1$)^(..+)

Keep only powers whose degree is at least 2. Note that the r flag reverses the direction of processing, as if the entire regex was in a lookbehind.

%`1

Convert to decimal.

naffetS · Accepted Answer · 2022-05-12 21:03:17Z

Python, 87 82 bytes

lambda n:[m for k in range(4,n*n)if 9<int(str(m:=(k//n)**(k%n))[::-1])==m<n>k%n>1]

Attempt This Online!

Brute-force. Extremely slow. \$O\Big(n^2\Big)\$.

-5 bytes thanks to jezza_99

Here's a much, much, much faster one:

Python, 128 bytes

import sympy.ntheory as s,math lambda x:[x for x in range(10,x)if math.gcd(*s.factorint(x).values())!=1and str(x)==str(x)[::-1]]

Attempt This Online!

\$O\Big(n\Big)\$.

\$\begingroup\$ 82 bytes \$\endgroup\$

jezza_99
– jezza_99

2022-05-12 20:34:30 +00:00
Commented May 12, 2022 at 20:34 — jezza_99
– jezza_99, Commented May 12, 2022 at 20:34

MarcMush · Accepted Answer · 2022-05-13 13:12:28Z

Julia 1.0, 55 bytes

!n=filter(i->"$i"==reverse("$i")&&i∈(r=2:i)'.^r,10:n)

Try it online!

with a beautiful \$O(n^3)\$ complexity and \$O(n^2)\$ memory usage

Arnauld · Accepted Answer · 2022-05-13 22:29:07Z

JavaScript (V8), 81 bytes

n=>(g=x=>(x*=p)<n?[...x+''].reverse(g(x)).join``==x&&print(x):++p*p<n&&g(p))(p=7)

Try it online!

Note

For \$n<7\$, there is no \$k\$ such that \$n^k\$ is a palindromic power less than \$100000000\$ with at least 2 decimal digits. Therefore, we can safely start the search with \$n=7\$ and get rid of the few single-digit palindromic powers (\$2^2\$, \$2^3\$, \$3^2\$).

Commented

n => ( // n = upper bound g = // g is a recursive function taking x => // the current result x (x *= p) < n ? // multiply x by p; if it's less than n: [...x + ''] // turn x into an array of digits .reverse( // reverse this array g(x) // do a recursive call with x unchanged ) // (reverse() ignores this argument) .join`` == x && // if x is palindromic: print(x) // print it : // else: ++p * p < n && // increment p; if p² is less than n: g(p) // do a recursive call with x = p // (otherwise, stop the recursion) )(p = 7) // initial call to g with x = p = 7

Huh, I would have thought that the conjecture only allowed you to only consider squares and cubes but instead you skip powers of 2, 3, 4, 5 and 6? — Neil
– Neil, Commented May 13, 2022 at 12:44
@Neil [edited] Yes, because none of them leads to a palindromic power \$n^k\$ with at least 2 decimal digits for \$k\le 4\$, while we get single-digit powers that need to be filtered out with \$n=2\$ and \$n=3\$. It allows me to get rid of the test x>9. — Arnauld
– Arnauld, Commented May 13, 2022 at 13:16
@Neil PS: I didn't notice there was an upper bound on the input. So starting at 7 is safe anyway, no matter if the conjecture is true or not. — Arnauld
– Arnauld, Commented May 13, 2022 at 22:33

lyxal · Accepted Answer · 2022-05-12 01:41:49Z

Vyxal, 16 bytes

ɽ₀ȯ'ɽ›Ėe:⌊=anḂ=∧

Try it Online!

Who needs smart prime factorisation when you can just brute force it?

Explained

ɽ₀ȯ'ɽ›Ėe:⌊=anḂ=∧ ɽ₀ȯ' # From the range [11, n) (empty if n < 10) keep only items (x) where: ɽ›Ėe:⌊=a # there exists a number in the range [2, x) where that number to an integer power equals x nḂ=∧ # and x is a palindrome

The part which checks for important power better explained:

ɽ›Ėe:⌊= ɽ› # the range [2, x) Ė # the reciprocal of each number in that range - no need to worry about floating point accuracy errors because everything is stored as fractions internally e # x to the power of each of those reciprocals - this is taking every nth root of x which is less than x :⌊= # determine whether each item is a whole integer.

your link doesn't have any input. you might also add the T flag to extend timeout to 1 min — naffetS
– naffetS, Commented May 12, 2022 at 1:16
@steffan I know it doesn't have any input - it would time out for any input anyway — lyxal
– lyxal ♦, Commented May 12, 2022 at 1:17

naffetS · Accepted Answer · 2022-05-12 17:17:22Z

Ruby `-rprime`, 88 bytes

->x{(10..x).select{|y|y.prime_division.map(&:last).inject(:gcd)>1&&y.digits*''==y.to_s}}

Attempt This Online!

Neil · Accepted Answer · 2022-05-12 19:52:18Z

Charcoal, 19 bytes

ＩΦ…χＮ›⁼ι⮌ι⬤…²ι⊖Σ↨ιλ

Try it online! Link is to verbose version of code. Very brute force. Explanation:

 … Range from χ Predefined variable `10` to Ｎ Input as a number Φ Filtered where ι Current value ⁼ Equals ι Current value ⮌ Reversed › And not … Range from ² Literal integer `2` to ι Current value ⬤ All value satisfy ι Outer value ↨ Converted to base λ Inner value Σ Take the sum ⊖ Is not equal to `1` Ｉ Cast to string Implicitly print each match on its own line

A more efficient version for 28 bytes:

ＩΦ…χＮ∧⁼ι⮌ι⊙↨ι²⁼¹Σ↨ι⌈Ｘ⊖ι∕¹⁺²μ

Try it online! Link is to verbose version of code. Explanation: Works by only testing 20 (for n=1000000) approximate roots for each palindrome instead of all n.

If the conjecture mentioned by @Arnauld is true then the efficient version can be improved in speed by replacing ↨ι² with 23 and ⁺²μ with Ｉλ, also saving two bytes. — Neil
– Neil, Commented May 13, 2022 at 12:38

Kevin Cruijssen · Accepted Answer · 2022-05-13 07:40:21Z

Java 8, 133 bytes

n->{for(;--n>9;)for(int t=2,i=2;(n+"").contains(new StringBuffer(n+"").reverse())&i<n;t=t>n?++i:t*i)if(t==n)System.out.println(i=n);}

Outputs in reversed order. Very slow for larger test cases.

Inspired by @att's C answer.

Try it online.

Explanation:

n->{ // Method with integer parameter and no return-type for(;--n>9;) // Loop `n` downward in the range (n,9): for(int t=2,i=2;// Create two temp integers, starting at 2 (n+"").contains(new StringBuffer(n+"").reverse())& // If the current `n` is a palindrome: i<n // Inner loop as long as `i` is still smaller than `n`: ; // After every iteration: t= // Replace `t` with: t>n? // If `t` is larger than `n`: ++i // Increase `i` by 1 first, and set `t` to this new `i` : // Else: t*i) // Multiply `t` by `i` if(t==n) // If `t` is equal to the current `n`: System.out.println( i=n // Set `i` to the current `n` );} // And print it with trailing newline

DeathIncarnate · Accepted Answer · 2022-05-14 20:46:16Z

Burlesque, 48 bytes

-.{J<-==}FO9.-f{Jbcjfc:-.jqLGZ]{J@1.>jXXsm&&}ay}

Try it online!

-. # Decrement {J<-==}FO # Filter palindromes 9.- # Drop single digits f{ # Filter J # Duplicate bc # Repeat infinitely jfc # Factors :-. # Greater than 1 jqLGZ] # Log of number against factor { J@1.> # Greater than 1 jXXsm # Is whole number &&} # And ay # Any }

Jordan · Accepted Answer · 2022-11-18 19:17:34Z

J-uby `-rprime`, 85 bytes

Port of Steffan’s Ruby answer.

:!~&10|:select+(-[:prime_division|:*&:last|:/&:gcd|:<&1,:==%[:digits|:join,S]]|:all?)

Attempt This Online!

Palindromic Powers

Powers

Palindrome

Palindromic Power

Example

Your Challenge

Example Program

Input

Scoring

19 Answers 19

Desmos, 177 175 bytes

05AB1E, 11 bytes

How?

Jelly, 13 bytes

How it works

Factor + math.primes.factors project-euler.common, 101 102 bytes

Wolfram Language (Mathematica), 60 bytes

Vyxal, 14 bytes

How?

C (gcc), 117 bytes

Ungolfed

Haskell, 76 72 64 bytes

Explanation:

C (gcc), 111 bytes

Retina 0.8.2, 100 bytes

Python, 87 82 bytes

Here's a much, much, much faster one:

Python, 128 bytes

Julia 1.0, 55 bytes

JavaScript (V8), 81 bytes

Note

Commented

Vyxal, 16 bytes

Explained

Ruby -rprime, 88 bytes

Charcoal, 19 bytes

Java 8, 133 bytes

Burlesque, 48 bytes

J-uby -rprime, 85 bytes

Linked

Related

Hot Network Questions

Factor + `math.primes.factors project-euler.common`, 101 102 bytes

Ruby `-rprime`, 88 bytes

J-uby `-rprime`, 85 bytes