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:

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 coinheringaahin g, May 12, 2022 at 0:46
I think there is a way around this, I will change the code later. — Number Basher, 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, 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

8

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?

edited May 12, 2022 at 15:55

answered May 12, 2022 at 2:07

naffetS

11.7k2 gold badges16 silver badges47 bronze badges

1

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

Add a comment |

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

6

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

edited May 13, 2022 at 16:59

answered May 12, 2022 at 0:37

caird coinheringaahin g♦

48.4k10 gold badges114 silver badges339 bronze badges

\$\begingroup\$ Yep, I see. I will run it to try. \$\endgroup\$
– Number Basher
May 12, 2022 at 0:39
\$\begingroup\$ 13 bytes (much quicker too). \$\endgroup\$
– Jonathan Allan
May 13, 2022 at 12:29
\$\begingroup\$ @JonathanAllan Nice one, I always forget the double filter trick \$\endgroup\$
– caird coinheringaahin g ♦
May 13, 2022 at 12:35

Add a comment |

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

4

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

edited May 12, 2022 at 5:08

answered May 12, 2022 at 2:45

att

18.2k2 gold badges13 silver badges53 bronze badges

Add a comment |

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

3

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?

edited May 12, 2022 at 1:55

answered May 12, 2022 at 1:03

naffetS

11.7k2 gold badges16 silver badges47 bronze badges

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

Add a comment |

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

3

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!

answered May 12, 2022 at 22:33

att

18.2k2 gold badges13 silver badges53 bronze badges

Add a comment |

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

2

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)\$.

edited May 12, 2022 at 21:03

answered May 12, 2022 at 16:57

naffetS

11.7k2 gold badges16 silver badges47 bronze badges

\$\begingroup\$ 82 bytes \$\endgroup\$
– jezza_99
May 12, 2022 at 20:34

Add a comment |

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

2

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

answered May 13, 2022 at 13:12

MarcMush

5,7149 silver badges15 bronze badges

Add a comment |

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, 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, 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, May 13, 2022 at 22:33

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

1

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.

edited May 12, 2022 at 1:41

answered May 12, 2022 at 1:13

lyxal

27.6k2 gold badges51 silver badges130 bronze badges

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

Add a comment |

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

1

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!

answered May 12, 2022 at 17:17

naffetS

11.7k2 gold badges16 silver badges47 bronze badges

Add a comment |

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, 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

1

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
 }

answered May 14, 2022 at 20:46

DeathIncarnate

2,5006 silver badges9 bronze badges

Add a comment |

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

0

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!

edited Nov 18, 2022 at 19:17

answered Nov 18, 2022 at 16:28

Jordan

9,2461 gold badge29 silver badges47 bronze badges

Add a comment |

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

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfnumbersequencearithmeticpalindrome or ask your own question.

Linked

Related

Hot Network Questions

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

Ruby `-rprime`, 88 bytes

J-uby `-rprime`, 85 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
number
sequence
arithmetic
palindrome
or ask your own question.