4
\$\begingroup\$

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 .

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Your example program is prone to floating point errors, due to the log and the is_integer check \$\endgroup\$ May 12 at 0:46
  • \$\begingroup\$ I think there is a way around this, I will change the code later. \$\endgroup\$ May 12 at 0:53
  • 1
    \$\begingroup\$ Change DONE!!!! \$\endgroup\$ May 12 at 1:45
  • \$\begingroup\$ This is A075786 without the first 4 terms. \$\endgroup\$
    – Arnauld
    May 13 at 7:43
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ May 13 at 14:51

18 Answers 18

11
\$\begingroup\$

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

\$\endgroup\$
8
\$\begingroup\$

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?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Haha. I'm awake now, but I don't see any way to shorten your port. ;) +1 from me. \$\endgroup\$ May 12 at 6:32
6
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Yep, I see. I will run it to try. \$\endgroup\$ May 12 at 0:39
  • \$\begingroup\$ 13 bytes (much quicker too). \$\endgroup\$ May 13 at 12:29
  • \$\begingroup\$ @JonathanAllan Nice one, I always forget the double filter trick \$\endgroup\$ May 13 at 12:35
4
\$\begingroup\$

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])
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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?
\$\endgroup\$
1
  • \$\begingroup\$ ǐĠvL can now just be ∆ǐ in a newer version, but this challenge inspired the builtin. \$\endgroup\$
    – Steffan
    yesterday
3
\$\begingroup\$

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;
      }
    }
  }
}
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
2
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$
    – Neil
    May 13 at 12:44
  • \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    May 13 at 13:16
  • \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    May 13 at 22:33
1
\$\begingroup\$

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.    
\$\endgroup\$
3
  • \$\begingroup\$ your link doesn't have any input. you might also add the T flag to extend timeout to 1 min \$\endgroup\$
    – Steffan
    May 12 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 at 1:17
  • \$\begingroup\$ 121 doesn't time out for me with T flag \$\endgroup\$
    – Steffan
    May 12 at 1:17
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 19 bytes

IΦ…χN›⁼ι⮌ι⬤…²ι⊖Σ↨ιλ

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

  …                 Range from
   χ                Predefined variable `10` to
    N               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`
I                   Cast to string
                    Implicitly print each match on its own line

A more efficient version for 28 bytes:

IΦ…χN∧⁼ι⮌ι⊙↨ι²⁼¹Σ↨ι⌈X⊖ι∕¹⁺²μ

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.

\$\endgroup\$
1
  • \$\begingroup\$ If the conjecture mentioned by @Arnauld is true then the efficient version can be improved in speed by replacing ↨ι² with 23 and ⁺²μ with Iλ, also saving two bytes. \$\endgroup\$
    – Neil
    May 13 at 12:38
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
 }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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