The minimal power iteration of a number \$n\$ is defined as follows:

$$\text{MPI}(n):=n^{\text{min}(\text{digits}(n))}$$

That is, \$n\$ raised to the lowest digit in \$n\$. For example, \$\text{MPI}(32)=32^2=1024\$ and \$\text{MPI}(1234)=1234^1=1234\$.

The minimal power root of a number \$n\$ is defined as the number obtained from repeatedly applying \$\text{MPI}\$ until a fixed point is found. Here is a table of the minimal power roots of numbers between 1 and 25:

   n              MPR(n)
--------------------------
   1                   1
   2                   1
   3              531441
   4                   1
   5                3125
   6 4738381338321616896
   7                   1
   8            16777216
   9                   1
  10                   1
  11                  11
  12                  12
  13                  13
  14                  14
  15                  15
  16                  16
  17                  17
  18                  18
  19                  19
  20                   1
  21                  21
  22                   1
  23              279841
  24                   1
  25                   1

Challenge: Generate the numbers whose minimal power root is not equal to 1 or itself.

Here are the first 50 numbers in this sequence:

3, 5, 6, 8, 23, 26, 27, 29, 35, 36, 39, 42, 47, 53, 59, 64, 72, 76, 78, 82, 83, 84, 92, 222, 223, 227, 228, 229, 233, 237, 239, 254, 263, 267, 268, 269, 273, 276, 277, 278, 279, 285, 286, 287, 289, 296, 335, 338, 339, 342

Rules

  • You may generate the first n numbers of this sequence (0- or 1-indexed), generate the nth term, create a generator which calculates these terms, output infinitely many of them, etc.
  • You may take input and give output in any base, but the calculations for MPR must be in base 10. E.g., you may take input ### (in unary) and output ### ##### ###### (in unary)
  • You must yield numbers. You may not (e.g.) output "3", "5", "6", since those are strings. 3, 5, 6 and 3 5 6 are both valid, however. Outputting 2 3, "23", or twenty-three are all considered invalid representations of the number 23. (Again, you may use any base to represent these numbers.)
  • This is a , so the shortest code (in bytes) wins.
  • 2
    Just curious, how could you prove that a fixed point is found eventually for all n? – nwellnhof Oct 14 at 22:23
  • 1
    @nwellnhof (Rough proof.) Suppose there is no fixed point of \$x\$, i.e., \$\text{MPR}(x)\$ doesn't exist. Let \$x_i\$ be the \$i\$-th iteration of the \$\text{MPI}\$ function over \$x\$. This sequence is strictly increasing, since \$a^b>a^{b^c}\$ for all \$a,b,c\ge2\$. Being strictly increasing, the probability of no digit in \$x_i\$ being 0 or 1 tends towards 0 as \$x_i\$ tends towards \$\infty\$. – Conor O'Brien Oct 14 at 22:39
  • Huh. The oeis doesn't have this sequence. – Draco18s Oct 15 at 0:09
  • @ConorO'Brien That shows your hypothesis is plausible, but it doesn't prove it. – kasperd Oct 15 at 15:37
  • 1
    @kasperd Thus the "rough proof" before it. – Conor O'Brien Oct 15 at 20:13

23 Answers 23

Perl 6, 49 bytes

{grep {($_,{$_**.comb.min}...*==*).tail>$_},1..*}

Try it online!

Returns an infinite sequence. I suppose that the following 45 byte version works, too, but I can't prove that the fixed point is always found after n iterations.

{grep {($_,{$_**.comb.min}...*)[$_]>$_},3..*}

05AB1E, 8 bytes

Generates the nth number 1-indexed

µNÐΔWm}‹

Try it online!

Explanation

µ          # run until counter equals input
 NÐ        # push 3 copies of the current iteration index (1-based)
   Δ  }    # run this code until the result no longer changes     
    Wm     # raise the number to the power of its minimum digit
       ‹   # check if greater than the index

Optionally as an infinite list at the same byte count:

∞ʒDΔWm}‹

Try it online!

  • Wait, is that all?.. That looks so much simpeler than I thought it would be.. >.> I'll delete my answer, since it's more than twice as long.. – Kevin Cruijssen Oct 15 at 12:48
  • @KevinCruijssen: I am a bit surprised myself. Thought it would take 12 or so bytes when looking at the task. – Emigna Oct 15 at 13:44
  • 1
    I twiddled with µ and Δ right after the challenge was posted and got this exact same answer, but I was wondering why it didn't work... I used D rather than Ð because I thought one copy would have been used by the fixed-point function and the other by the smaller-than function, but I didn't take into account that I needed yet another copy. Thanks, Emigna, for solving my Enimga. – Mr. Xcoder Oct 15 at 17:13

Pyth, 10 bytes

.f>u^GshS`

Try it online!

This generates a list of the first \$ n \$ such numbers. The auto-filled program has GZZQ as a suffix. This simply finds (.f) the first Q numbers that have a minimal power root u^GshS`G greater than itself Z.

The minimal power root code works by finding a fixed point u of raising the current number G to the power of it's minimal digit, which is the same as the first digit (h) sorted lexicographically (S), then converted back to an integer (s).

Jelly, 10 bytes

*DṂƊƬḊCȦµ#

A monadic Link taking an integer, I, from STDIN which yields the first I entries.

Try it online!

(*DṂƊƬṪ%@µ# works for 10 too)

How?

Counts up starting a n=0 until input truthy results of a monadic function are encountered and yields those ns.

The function repeatedly applies another monadic function starting with x=n and collects the values of x until the results are no longer unique. (e.g.: 19 yields [19]; 23 yields [23,529,279841]; 24 yields [24, 576, 63403380965376, 1]; etc...) and then dequeues the result (removes the leftmost value), complements all the values (1-x) and uses Ȧ to yield 0 when there is a zero in the list or if it's empty.

The innermost function raises the current x to all the digits of x and then keeps the minimum (doing this is a byte save over finding the minimum digit first).

*DṂƊƬḊCȦµ# - Link (call the input number I)
         # - count up from 0 and yield the first I for which this yields a truthy value:
        µ  -   a monadic chain:
    Ƭ      -     collect until results are not unique:
   Ɗ       -       last three links as a monad:
 D         -         convert to a list of decimal digits
*          -         exponentiate
  Ṃ        -         minimum
     Ḋ     -     dequeue
      C    -     compliment
       Ȧ   -     any-and-all?

J, 41 39 37 bytes

(>:[echo^:(<(^0".@{/:~@":)^:_))^:_]1x

Try it online!

This one is a full program printing the infinite sequence. A very rare occasion where a full program beats a verb in J.

How it works

(>:[echo^:(<mpi_fix))^:_]1x    Using the mpi_fix below; it finds the MPI fixpoint
          (<mpi_fix)           Is mpi_fix greater than the input?
    echo^:                     If so, apply echo; do nothing otherwise
                               echo returns an empty array
 >:[                           Discard the above and return input+1
(                   )^:_       Repeat the above infinitely (increment has no fixpoint)
                        ]1x    starting from arbitrary-precision number 1

J, 41 39 bytes

>:^:(>:(^0".@{/:~@":)^:_)^:_@>:@]^:[&0x

Try it online!

A monadic verb. Given a 1-based index, returns the number at that index. The footer checks that first 20 terms are correct.

Reading the word "fixpoint", I immediately thought "Oh yeah, ^:_ will do the great job." Then I ended up with this abomination of angry and sad faces. And it's not even a train, it's a single verb.

Ungolfed & How it works

nth_term =: >:^:(>:(^0".@{/:~@":)^:_)^:_@>:@]^:[&0x

mpi =: ^0".@{/:~@":    Find the MPI
             /:~@":    Sort the string representation
        0   {          Take first item
         ".@           Convert back to number
       ^               Raise the input to the power of above

mpi_fix =: mpi^:_      Find the MPI fixpoint

next_term =: >:^:(>:mpi_fix)^:_@>:    Given a number, find the next term
                               @>:    Increment once, and then...
                  >:mpi_fix           Is mpi_fix not greater than input?
             >:^:           ^:_       Increment while the above is true

nth_term =: next_term@]^:[&0x    Given one-based index, find the nth term
            next_term@]          Apply next_term monadically
                       ^:[       n times
                          &0x    to the starting value of zero

The arbitrary-precision integer 0x is needed to compute the fixpoint accurately, e.g. of the number 6.

Mathematica, 59 51 bytes

-8 bytes thanks to Misha Lavrov.

Select[Range@#,#<(#//.x_:>x^Min@IntegerDigits@x)&]&

Pure function. Takes a number as input, and returns the list of terms up to that number as output. Nothing very complicated here.

  • FixedPoint is usually not as good as //. (short for ReplaceRepeated) in code golf. Here, we may save a few bytes with Select[Range@#,1<(#//.x_:>x^Min@IntegerDigits@x)!=#&]&. – Misha Lavrov Oct 15 at 1:34
  • Also, if MPI(x) is neither 1 nor x, then it is always bigger than x, so an even shorter solution is Select[Range@#,#<(#//.x_:>x^Min@IntegerDigits@x)&]&. – Misha Lavrov Oct 15 at 1:37
  • @MishaLavrov Thanks! – LegionMammal978 Oct 15 at 10:02

Python 3, 90 88 bytes

-2 bytes by @mypetlion

def F(x):m=x**int(min(str(x)));return[int,F][m>x](m)
x=1
while 1:x<F(x)and print(x);x+=1

Try it online!

print as an expression saves two bytes over using if statement in Python 2. F computes the MPI fixpoint; the rest gives the infinite sequence to STDOUT.

  • Change return m>x and F(m)or m to return[int,F][m>x](m) to save 2 bytes. – mypetlion Oct 15 at 18:35
  • 78 bytes – Lynn Oct 17 at 11:29

Haskell, 67 62 bytes

filter((<)<*>until((==)=<<g)g)[1..]
g a=a^read[minimum$show a]

Returns an infinite list.

Try it online!

Ruby, 52 bytes

x=1;loop{b=x+=1;1while b<b**=b.digits.min;b>x&&p(x)}

Try it online!

Prints infinite sequence

Java 10, 178 173 bytes

v->{for(int x=1,m;;){var b=new java.math.BigInteger(++x+"");for(m=9;m>1;)b=b.pow(m=(b+"").chars().min().orElse(0)-48);if(b.compareTo(b.valueOf(x))>0)System.out.println(x);}}

Port of @GB's Ruby answer, so also prints indefinitely.

Try it online.

Explanation:

v->{             // Method with empty unused parameter and no return-type
  for(int x=1,   //  Start an integer `x` at 1
      m;         //  Temp integer for the smallest digit, starting uninitialized
      ;){        //  Loop indefinitely
    var b=new java.math.BigInteger(++x 
                 //   Increase `x` by 1 first
          +"");  //   And create a BigInteger `b` for the new `x`
    for(m=9;     //   Reset `m` to 9
        m>1;)    //   Loop as long as the smallest digit is not 0 nor 1
      b=b.pow(m=(b+"").chars().min().orElse(0)-48
                 //    Set `m` to the smallest digit in `b`
              ); //    Set `b` to `b` to the power of digit `m`
    if(b.compareTo(b.valueOf(x))>0)
                 //   If `b` is larger than `x`:
      System.out.println(x);}}
                 //    Print `x` with a trailing newline

JavaScript (Node.js), 75 bytes

Returns the \$n\$th term, 1-indexed.

f=(i,x=n=1n)=>(N=x**BigInt(Math.min(...x+'')))>x?f(i,N):(i-=N>n)?f(i,++n):n

Try it online!

JavaScript (Node.js), 98 90 89 86 bytes

-3 bytes thanks @Conor O'Brien

function*(){for(n=0n;;x>n&&(yield n))for(x=++n;(b=Math.min(...""+x))-1;)x**=BigInt(b)}

Try it online!

Using the fact that \$MPR(n)>n\$ if \$MPR(n)\notin \{1,n\}\$

Seems that a generator is shorter than returning an array of n numbers?

Or printing infinitely - 72 bytes

for(n=0n;;x>n&&alert(n))for(x=++n;(b=Math.min(...""+x))-1;)x**=BigInt(b)

Try it online!

  • 86 bytes by moving some of the control flow around, eliminating braces. (mainly: if(x>n)yield n to x>n&&(yield n) as an expression) – Conor O'Brien Oct 15 at 20:18

Jelly, 14 bytes

3*DṂ$$ÐLḟ1,$Ɗ#

Try it online!

JavaScript (Chrome), 78 77 bytes

F=x=>(m=x**BigInt(Math.min(...''+x)))>x?F(m):m
for(x=0n;++x;)x<F(x)&&alert(x)

Try it online!

Port of my own Python 3 solution. The latest version of Chrome supports BigInt (tested on my PC). Don't try this code as-is on your browser though.

Racket, 270, 257 233 bytes

(define(f n)(local((define(m x)(expt x(-(first(sort(map char->integer(string->list(~v x)))<))48)))(define(g y)(if(= y(m y))y(g(m y))))(define(k x l)(if(=(length l)n)l(if(< x(g x))(k(+ x 1)(cons x l))(k(+ x 1)l)))))(reverse(k 1'()))))

Try it online!

This is my first Racket submission, so it can definitely be golfed much further. Nevertheless I'm somewhat content, at least for managing to solve the task.

More readable:

(define (f n)
  (local ((define (m x)
           (expt x
                 (- (first (sort (map char->integer (string->list (~v x)))
                                 <))
                    48)))
         (define (g y)
           (if
             (= y (m y))
             y
             (g (m y))))
         (define (k x l)
           (if (= (length l) n)
               l
               (if (< x (g x))
                   (k (+ x 1) (cons x l))
                   (k (+ x 1) l))))
    (reverse (k 1 '()))))

Axiom, 168 bytes

u(x)==(y:=x::String;x^reduce(min,[ord(y.i)-48 for i in 1..#y])::NNI)
q(a:PI):PI==(b:=a;repeat(c:=u(b);c=b=>break;b:=c);b)
z(x)==[i for i in 1..x|(m:=q(i))~=1 and m~=i]

The function to use it is z(); here it print numbers that has the corrispondence one number not 1, not itself and are less than its argument.

(6) -> z 1000
 (6)
 [3, 5, 6, 8, 23, 26, 27, 29, 35, 36, 39, 42, 47, 53, 59, 64, 72, 76, 78, 82,
  83, 84, 92, 222, 223, 227, 228, 229, 233, 237, 239, 254, 263, 267, 268,
  269, 273, 276, 277, 278, 279, 285, 286, 287, 289, 296, 335, 338, 339, 342,
  346, 347, 348, 354, 358, 363, 365, 372, 373, 374, 376, 382, 383, 386, 392,
  394, 395, 399, 423, 424, 426, 427, 428, 432, 433, 435, 436, 442, 447, 459,
  462, 464, 466, 467, 468, 469, 476, 477, 479, 483, 487, 488, 489, 493, 494,
  523, 524, 527, 529, 533, 537, 542, 546, 553, 556, 557, 562, 563, 572, 573,
  577, 582, 583, 584, 594, 595, 598, 623, 626, 627, 629, 632, 633, 642, 646,
  647, 648, 663, 664, 669, 672, 676, 682, 683, 684, 693, 694, 695, 698, 722,
  724, 729, 736, 759, 763, 773, 775, 782, 786, 823, 829, 835, 846, 847, 856,
  873, 876, 885, 893, 894, 896, 923, 924, 928, 933, 953, 954, 962, 969, 973,
  974, 984, 993, 994, 995]
                                               Type: List PositiveInteger

Visual Basic .NET (.NET Core), 290 bytes (includes imports)

Iterator Function A()As System.Collections.IEnumerable
Dim i=B.One,q=i,p=i
While 1=1
q=i-1
p=i
While q<>p
For j=0To 9
If p.ToString.Contains(j)Then
q=p
p=B.Pow(p,j)
Exit For
End If
Next
End While
If p>1And p<>i Then Yield i
i+=1
End While
End Function

Try it online!

Requires the following import:

Imports B = System.Numerics.BigInteger

This uses an iterator function to return an infinite (lazy loaded) list of integers that meets the criteria. Uses BigInteger to avoid any size restrictions, particularly with intermediate calculations.

Un-golfed:

Iterator Function A() As System.Collections.IEnumerable
    Dim i As B = 1
    While True
        Dim prevProduct As B = 0
        Dim product As B = i
        While prevProduct <> product
            For j = 0 To 9
                If product.ToString.Contains(j) Then
                    prevProduct = product
                    product = B.Pow(product, j)
                    Exit For
                End If
            Next
        End While
        If product <> 1 And product <> i Then
            Yield i
        End If
        i += 1
    End While
End Function

Common Lisp, 238 bytes

(defun x(m n o p q)(setf i(sort(map 'list #'digit-char-p(prin1-to-string m))#'<))(setf j(expt m(first i)))(cond((= q p)nil)((and(= n j)(not(= n 1))(not(= n o)))(cons o(x(1+ o)0(1+ o)p(1+ q))))((= n j)(x(1+ o)0(1+ o)p q))(t(x j j o p q))))

Try it online!

APL(NARS), 96 chars, 192 bytes

r←f w;k;i;a
   r←⍬⋄k←1
A: i←k
B: →C×⍳i=a←i*⌊/⍎¨⍕i⋄i←a⋄→B
C: →D×⍳(a=k)∨a=1⋄r←r,k
D: k+←1⋄→A×⍳k≤w

test (partial result for argument 22 seems to much big so <21 arguments I don't know if can be ok)

  f 21
3 5 6 8 

Python 3, 102 bytes

x=int(input())
a=c=0
while x:
 a+=1;b=a
 while b-c:b,c=b**int(min(str(b))),b
 x-=b!=1and b!=a
print(a)

Try it online!

Decided to try a Python 3 solution that directly prints the nth term in the sequence.

C (clang) + -DL=long long -lm, 213 bytes

q(char*a,char*b){return*a>*b;}L f(L a){char*c;asprintf(&c,"%lld",a);qsort(c,strlen(c),1,q);L b=pow(a,*c-48);return b>a?f(b):b;}i;g(j){for(i=0;j;i++){L x=f(i);x!=i&x!=1&x>0&&printf("%d\n",i)&&j--;}}

Try it online!

Function g(j) prints the first j terms of the sequence.

  • Return with a=... to save a dozen or so bytes. – Rogem Oct 20 at 12:05
  • And x>1 instead of x!=1&x>0. – Rogem Oct 20 at 12:13
  • The first one requires a change to GCC, though. – Rogem Oct 20 at 12:20

Husk, 16 12 10 bytes

fS>ωṠ^o▼dN

Saved 6 bytes thanks to H.PWiz.
Try it online!

Explanation

fS>ωṠ^o▼dN
f        N       Filter the natural numbers where...
   ω             ... the fixed point...
    Ṡ^o▼d        ... of raising the number to its smallest digit...
 S>              ... is greater than the number.
  • You can change here with S>. This allows you to put it all in one line. Also, it appears that you have mistakenly left in the previous tio link – H.PWiz Oct 17 at 21:27

Japt, 44 bytes


_ì ñ g
_gV ¥1?Z:ZpZgV)gW
@@[1X]øXgW}fXÄ}gUÄ

Try it online!

Substantially different from the other Japt answer.

Explanation:

                        Empty line preserves the input

_ì ñ g                Function V finds the smallest digit in a number Z
 ì                          Get the digits of Z
   ñ                        Sort the digits
     g                      Get the first (smallest) digit


_gV ¥1?Z:ZpZgV)gW     Function W finds the MPR of a number Z
 gV ¥1?Z                    If V(Z) is 1, then it's stable; return it
        :ZpZgV)             Otherwise get MPI of Z...
               gW           And call W on it ( MPR(Z) == MPR(MPI(Z)) )

@@[1X]øXgW}fXÄ}gUÄ    Main program
@             }gUÄ      Get the nth number by repeatedly applying...    
 @        }fXÄ              Find the next smallest number X which returns false to...
       XgW                    MPR(X)
      ø                       is either...
  [1X]                        1 or X

In terms of future golfing possibilities, I do a lot of manually calling a function on a number, which I suspect could be reduced but I'm not sure how.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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