Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The winner (pretty obviously) is Dennis ♦, who used Jelly with 10 bytes!

This challenge will still be up here, however results won't be taken anymore.


The powertrain of a number is a concept by John Conway (who is also notable for making Conway's Game of Life, but that's not the point). It is defined as so:

For any number enter image description here..., the powertrain of the number is enter image description here... (i.e. every 2nd digit, from left to right, is a power of the digit before that). This process is repeated until the result is a single digit.

EXAMPLES:

2592 => (2^5)(9^2) = 2592 <= Cannot be further decomposed 135 => (1^3)5 = 5 1234 => (1^2)(3^4) = 81 => (8^1) = 8 1100 => (1^1)(0^0) = 1 # (0^0) = 1 -42 => -42 # Negative numbers output the input

Your challenge is, for any number n in the input, return powertrain(n) (i.e. n after the powertrain decomposition is finished) as output.

This is code golf, so shortest amount of bytes wins.

DISCLAIMER-THINGS:

  • You can have an odd number of digits in the input, the last digit just won't have a power.
  • 0^0 is 1, because if it was 0, then a lot of numbers would instantly collapse to 0 or 1.
  • If the number is indestructible in any part of the computation process (e.g. if it ends up with 2592), then you can just output the number.
  • If the input is < 10 (i.e. all single digit numbers and negatives), output the input.

I'll probably announce a winner after a few hours days.

Current leaderboard:

  1. Jelly (Dennis ♦): 10
  2. Pyth (DenkerAffe): 16
  3. MATL (Don Muesli): 21
  4. Perl (Ton Hospel): 42
  5. Haskell (Damien): 64
  6. Javascript ES6 (edc65): 71
  7. Mathematica (murphy): 74
  8. Mathematica (LegionMammal978) and Haskell (Renzeee): 77
  9. Python 2 (mathmandan): 111
  10. Python 3 (Erwan): 161
  11. Java 8 (Blue): 229
  12. Oracle SQL 11.2 (Jeto): 456
  13. Befunge '93 (Lex): 490
share|improve this question
    
Some more test cases would be appreciated. – Mego Mar 8 at 7:34
    
So the input will have 4 digits max? – DenkerAffe Mar 8 at 7:42
7  
What if a cycle is reached, but the period of the cycle is not 1, or the input number is not part of the cycle? – feersum Mar 8 at 7:44
1  
"I'm certain there aren't any within the realms of feasibility". Can we assume it will never happen? I.e. allowing the loop to go on forever if a cycle of period > 1 is reached? – Stewie Griffin Mar 8 at 8:01
6  
Proposed test cases: 1100 and -42 It's easy to miss rules about edge cases if the do not show up in the test cases. – Dennis Mar 8 at 13:24

14 Answers 14

up vote 2 down vote accepted

Jelly, 15 14 12 10 bytes

Ds2*/€Pµ³¡

Try it online!

How it works

Ds2*/€Pµ³¡  Main link. Argument: n

D           Convert n into the array of its decimal digits.
 s2         Split into pairs of digits.
   */€      Reduce each pair by exponentiation.
      P     Take the product of the resulting powers.
       µ    Push the preceding chain as a link, and start a new one.
        ³¡  Execute the link n times and return the last result.
share|improve this answer
    
This could be made shorter by simply iterating n times, but I don't have a proof that it works for all possible inputs. – Dennis Mar 8 at 13:55
1  
You should be ok for any reasonable number. In fact you are almost certainly ok for ANY number using 16 iterations: oeis.org/A133503 – Ton Hospel Mar 8 at 14:22
    
@Dennis Hm, that's what I do in my answer – Luis Mendo Mar 8 at 14:50
1  
@DonMuesli And now that I've thought about it, it probably works. The odds of getting a 0 and an odd index are overwhelming... – Dennis Mar 8 at 16:22
    
Can the number be from input instead of as an argument? – DerpfacePython Mar 9 at 1:49

Haskell, 67 64 bytes

(>>=(==))>>=until$p.show is an unnamed function taking an integer as input and returning its powertrain.

Saved 3 bytes thanks to Zgarb

p(x:y:r)=p[x]^p[y]*p r;p[]=1;p x=read x
(>>=(==))>>=until$p.show
share|improve this answer
1  
((==)=<<g) saves two bytes over (\n->g n==n). – Zgarb Mar 8 at 15:58
    
Wow, I'm not familiar with the ((->) r) instance of Monad. Thanks for the trick. – Damien Mar 8 at 16:36

Perl, 42 48 bytes

Include +2 for -lp (you can drop the -l too but I like newlines)

Run with input on STDIN, e.g.

perl -lp powertrain.pl <<< 1234

powertrain.pl:

s/\B/1&pos?"**":"*"/eg until++$.>($_=eval)

(on older perls you can also drop the space between the regex and until)

This won't be able to handle the fixed point 24547284284866560000000000 but that large a value won't work anyways because by that time perl switched to exponential notation.

The above version is will in fact work fast (at most 2592 loops) for all numbers that perl can represent without using exponential notation since it is proven that there are no fixed points between 2592 and 24547284284866560000000000 (https://oeis.org/A135385)

This does however assume something as yet unproven. In principle there could be a reduction that takes more than X=10^7 steps (it is conjectured that no non-fixed point takes more than 16 steps, https://oeis.org/A133503) whose value dips below X (but above 10^7) and then goes up again. If that is the case I must fall back to:

s/\B/1&pos?"**":"*"/eg until$s{$_=eval}++||/-/

Explanation

The code works by putting ** and * (alternating) between the digits

s/\B/1&pos?"**":"*"/eg

so 2592 becomes 2**5*9**2 and 12345 becomes 1**2*3**4*5. These are valid perl expressions that can be evaluated with

$_ = eval

(0**0 is 1 in perl). Then just put a loop around that with a counter that makes it expire. Since except for the fixed points the values go down extremely quickly the powertrain series converges before the counter gets a chance to really get going

share|improve this answer

Pyth, 25 18 11 16 bytes

?<Q0Qu*F^McjGT2Q

Try it here!

7 14 bytes saved with help from @Jakube

Explanation

?<Q0Qu*F^McjGT2Q   # Q = eval(input)

?<Q0Q              # If input is negative return Q
     u         Q   # apply the following function until we reach a cycle               
                   # starting value is Q and the current value is in G
           jGT     # split input into a list of digits
          c   2    # split into pairs of 2
        ^M         # compute the power for every pair
      *F           # compute the product of all powers

share|improve this answer
1  
Is Pyth basically just a golfed version of Python, except with minor changes? – DerpfacePython Mar 8 at 9:09
1  
@Jakube Thanks for the hints! :) Still early in the morning for me... – DenkerAffe Mar 8 at 9:20
    
@DerpfacePython Yea, kinda. Have a look at the docs if you wanna learn about it. – DenkerAffe Mar 8 at 9:21
    
@Jakube Thanks again! :) – DenkerAffe Mar 8 at 9:34
4  
@DerpfacePython Pyth started out as just "shortened Python", but to call it that now would be disingenuous. Pyth has significantly diverged from Python. – Mego Mar 8 at 17:33

Python 2, 111 bytes

def p(n,b=0,o=''):
 if n<1:return n
 for c in str(n):o+=c+'**'[b:];b=~b
 j=eval(o+'1');return p(j)if j-n else j

The idea is to make a string where the digits of n are separated by operations which alternate between * and **, and then eval that string. (Other solutions use this same idea; see for example Ton Hospel's Perl answer.)

So, the operation switches back and forth between '**'[0:], which is **, and '**'[-1:], which is just *.

However, by the end of the for-loop, the string ends with an operation (one or the other), so we either need to drop the last operation, or else add another digit, in order for the string to make sense.

Fortunately, appending a 1 on the end will work no matter which operation is last. (If you like, 1 is a one-sided identity from the right, for both multiplication and exponentiation. Another way of saying this is that powertrain(n) == powertrain(10*n + 1) for all n>0.)

Finally, if the result of the eval happens to be the same as the input (as in a length-1 cycle), the function terminates. Otherwise, the function calls itself on the result. (It will hang forever on any cycle of length > 1, but according to the OP's comments I am allowed to assume there are no such cycles.)

(Note: the above explanation works for single-digit positive integers, since a single-digit input n will be completed to n**1 which will result in a 1-cycle. However, we also need to accept non-positive input, so there's a condition at the beginning that short-circuits if the input is less than 1. We could eliminate that line, and save 17 bytes, if the input were guaranteed to be non-negative.)

share|improve this answer
    
This sounds biased, but... upvote for being Python 2. And it has an explanation. – DerpfacePython Mar 9 at 1:52
    
@DerpfacePython Thanks! (I guess this would work just as well in Python 3...) – mathmandan Mar 9 at 2:18

JavaScript (ES6) 71

A recursive function, stopping when a repetition is found. This could not work for longer loops (2 or more value repeating) but it seems this could not happen, at least in the limited range of javascript number precision (17 digits)

f=n=>[...n+'1'].map((c,i)=>i&1?r*=Math.pow(d,c):d=c,r=1)&&n-r?f(r):n

Test

f=n=>[...n+'1'].map((c,i)=>i&1?r*=Math.pow(d,c):d=c,r=1)&&n-r?f(r):n

function go()
{
  v=+I.value
  R.textContent=f(v)
}  

go()
<input id=I value="1234"><button onclick="go()">Go</button>
<span id=R></span>

share|improve this answer
    
Nice of that +'1' to kill two birds with one stone! – Neil Mar 11 at 22:38
    
I don't know whether you'd investigated it already but the best I could do with replace was 1 byte longer: f=n=>`${n}1`.replace(/../g,([x,y])=>r*=Math.pow(x,y),r=1)&&n-r?f(r):n – Neil Mar 11 at 22:45
    
@Neil I tried hard too, but that template string is a new idea ... – edc65 Mar 12 at 1:12

Java 8, 265 244 229 bytes

This is my first answer, but I have been reading this site for a while and think I know what I'm doing. At least it beats befunge and SQL...

Unfortunately, like other answers, this one does not work for 24547284284866560000000000 due to java'a built in restrictions on how large integers can get.

Saved 36 bytes thanks to @JackAmmo

public int p(int n){if(n<10)return n;int i=1,t=1,s=(int)Math.log10(n)+1,r[]=new int[s];for(;i<=s;){int a=(int)Math.pow(10,i);r[s-i++]=n%a/(a/10);}for(i=0;i<s-1;i++)t*=Math.pow(r[i],r[++i]);if(s%2==1)t*=r[s-1];return n==t?n:p(t);}

Ungolfed Explanation

public int powertrain(int input){
    //handles negative and 1-digit cases
    if(input<10)return input;
    //initialize output variable       
    int total=1;
    // get "length" of number. Shorter than getting length of string representation
    int size=(int)Math.log10(input)+1;
    //initialize array to store digits
    int[] array=new int[size];
    //Now, because Java doesn't have support
    // for the "**" operation, and the way of turning
    // an integer into a string takes too many bytes,
    // I decided just to put every digit into an array with
    // math and iterate from there
    for(int i=1;i<=size;){
        int place=(int)Math.pow(10,i);
        //crazy math. Saved 1 byte by incrementing i when accessed
        array[size-i++]=input%place/(place/10);
    }
    for(int i=0;i<size-1;i++)
        //This is where the train happens.
        //Saved 1 byte by incrementing while accessing 
        //again, instead of i+=2 and i+1
        total*=Math.pow(array[i],array[++i]);
    //Make sure last number isn't left out if size is odd
    if(size%2==1)
        total*=array[size-1];
    //if we end up with same number, stop.
    //otherwise, keep recurring
    return input==total?input:powertrain(total);
}
share|improve this answer
    
In your first if...else if(n<10)return n;else{...} the else is unneccessary since logically everything in that else block would only run anyway when n<10 is false. Removing the else and the 2 matching braces will save you 6 bytes. There's a similar situation with your last if...else if(n==t)return n;else return p(t); remove the else and the space after it to save another 5 bytes. In fact you can shorten it even further if you use the triadic operator instead of the if...else like so return n==t?n:p(t); – Jack Ammo Mar 13 at 0:27
    
you can save a few more bytes (17 i think) by declaring t,s,r, and the for loop's i together int t=i=1,s=(int)Math.log10(n)+1,r[]=new int[s];for(;i<=s;){...}for(i=0;...)... – Jack Ammo Mar 13 at 0:46
    
@JackAmmo I wasn't aware variables could be declared like that, I'll have to try it. Thanks for your help! – Blue Mar 13 at 0:59
    
yeah, you just have to be careful with the order of declaring them if you're using one to initialize another (like how r uses s to define it's length) – Jack Ammo Mar 13 at 1:07
    
for arbitrary large numbers, you should look into java's BigInteger class docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html – Jack Ammo Mar 13 at 2:05

MATL, 21 bytes

tt0>*:"V!UtQgv9L2#)^p

It may take a few seconds to produce the output.

Try it online!

This uses the following two tricks to reduce byte count at the expense of code efficiency:

  • Iterate n times instead of waiting until a cycle is found. This is acceptable as per OP's comments.
  • For an odd number of digits a final 1 would have to be appended to complete the final power operation. Instead of that, the number of added 1 is the number of digits. This ensures an even number, so all power operations can be done (even if the last ones are unnecessary 1^1 operations).

Code:

t         % implicitly take input x. Duplicate
t0>*      % duplicate. Is it greater than 0? Multiply. This gives 0 if input is negative,
          % or leaves the input unchanged otherwise
:         % Generate array [1,2,...,x]
"         % for each (repeat x times)
  V       %   convert x to string
  !       %   transpose into column char array
  U       %   convert each char into number
  tQg     %   duplicate. Add 1 so that no entry is zero. Convert to logical: gives ones
  v       %   concatenate vertically
  9L2#)   %   separate odd-indexed and even-indexed entries
  ^       %   element-wise power
  p       %   product of all entries
          % implicitly end for each
          % implicitly display
share|improve this answer
    
Uh... heh heh heh... when I said "loops of numbers", I meant numbers that went like this - a, b, a, b ad infinitum (more than one term). If one term is repeated, then you should output that number. Sorry if that wasn't really clear. – DerpfacePython Mar 11 at 23:26
    
If one term is repeated, I'm outputting that number. I output the result after many iterations – Luis Mendo Mar 12 at 14:04
    
Oh, I understand now... just asking, how many iterations would it be (approx.)? Because when I type in 2592 into the input, it doesn't seem to output anything for quite a while. – DerpfacePython Mar 13 at 0:51
    
The number of iterations is the input number, so 2592 in that case. Yes, it takes a while – Luis Mendo Mar 13 at 3:58

Mathematica, 77 bytes

Times@@(If[#2<1,1,#^#2]&)@@@Partition[IntegerDigits@#,2,2,1,1]&~FixedPoint~#&

Anonymous function. Not too complicated.

share|improve this answer
    
Even so, can I still have an explanation? – DerpfacePython Mar 14 at 9:05

Befunge 720 490 bytes

Couldn't resist to do one more after the Never tell me the odds thing. So, I've optimized the "ASCII-fier" of the previous one. In this case I saw no need to let the instruction pointer run over the digits to read them, so I haven't taken the effort to make them human readable. So it's more of a digitifier, now.

Again, if you guys want an explanation, let me know in the comments, I'll try to create some helpful descriptions. You can copy paste the code into the interpreter. I've found that the example 24547284284866560000000000 outputs 0, but that seems to be a problem with getting such a large value from a point on the grid, as you can clearly see the correct value being stored in the final steps.

v                                                    //top row is used for "variables"
>&:0`#v_.@                                           //initialize the counter                          
v     <                           g01_v#-p01:  <     //on our way back to the digitifier, check if we're done
>::>210p>55+%:10g0p-55+/:v            >10g.@         //digitifier, creates a series of ASCII characters at the top line, one for each digit in the source
        ^p01+1g01    _v#:<
v1$$                  <                              //forget some remainders of the digitifier, put 1 on the stack as a base of calculation
                      v p0-1g01-1g0-1g01*g0g01<      //taking powers of each pair of digit
>10g2-!#v_10g1-!#v_  1>                10g1-0g|
^                                  p01-2g01  *<
        >10g0g*  >                             ^     //extra multiplication with last digit if the number of digits was odd

This version also supports negative input. It's a great improvement on the previous version, if I say so myself. At least 1 bug was fixed and the size was reduced greatly.

share|improve this answer
    
How many bytes more will it take for the thing to input negative numbers? – DerpfacePython Mar 11 at 6:25
    
I'm not sure to be honest. I had some problems with negative numbers and writing them somewhere in the grid. I'll try it again. – Lex Mar 11 at 8:07
    
I just found another bug, too. I did manage to add support for negative numbers. I'll post an update soon! It'll probably be the same amount of bytes, since I count the entire grid. – Lex Mar 11 at 8:15

Haskell, 100 79 77 bytes

g x|x==h x=x|1<2=g$h x;h=i.map(read.(:[])).show;i[]=1;i[a]=a;i(a:b:c)=a^b*i c

Not golfed:

g x|x==h x=x|1<2=g$h x
h=i.map(read.(:[])).show
i[]=1
i[a]=a
i(a:b:c)=a^b*i c

This function splits the input into digits and does the trick via i.

EDIT: Thanks to nimi for some tips.

share|improve this answer
    
A few tips: a) i(a:[])=a is i[a]=a, b) no need for max 1, because 0^0 = 1 in Haskell, c) replace (:[]) with pure, d) move the let within g into a separate function and replace the if ... then ... else with guards: h=i.map(read.pure).show ; g x|x==h x=x|1<2=h x – nimi Mar 9 at 18:23
    
pure is not in Prelude, but the rest of the tips work, thanks. I was trying to do it with guards, but ended up using ; before the guard and that didn't work, but now I know how it should work. – Renzeee Mar 11 at 8:49
    
pure is in the Prelude that comes with base-4.8.2.0. Don't know when it was introduced. You don't need the ( ) in i([a])=a. – nimi Mar 11 at 17:02

Mathematica, 74 bytes

0~f~0=f[]=1
f@n_=n
f[a_,b_,c___]:=f[c]a^b
#//.i_/;i>0:>f@@IntegerDigits@i&

Explanation

This solution uses a helper function f, which takes the digits of the number as arguments and applies one iteration of the power train operation. The last line is a pure function that is crafted to exploit the ReplaceRepeated function (or //. for short), which applies a rule to an expression (in this case the argument # of the pure function) until it doesn't change anymore. The rule i_/;i>0:>f@@IntegerDigits@i replaces anything non-negative with the function f applied to its decimal digits.

share|improve this answer
    
Line 2 doesn't work (use :=) – CalculatorFeline Mar 14 at 1:00
    
Explanation, please? – DerpfacePython Mar 14 at 9:04
    
@CatsAreFluffy I don't see your problem with line 2. It works fine for me! – murphy Mar 14 at 9:54
    
SetDelayed::write: Tag Times in n f[a_,b_,c___] is Protected. >>, Set::write: Tag Times in 1 f[n_] is Protected. >> The second error disappears when i use :=vs=. – CalculatorFeline Mar 14 at 15:07
    
Sorry, can't reproduce that error. But your output indicates that the line-breaks are part of the problem. Please try the version with ;s instead of the line-breaks: 0~f~0=f[]=1;f@n_=n;f[a_,b_,c___]:=f[c]a^b;#//.i_/;i>0:>f@@IntegerDigits@i& – murphy Mar 14 at 18:54

Python 3, 169 161 bytes

def f(s):
 o=[['1',s]['-'in s]]
 while s not in o:
  o+=[s];s+='1'*(len(s)%2==1);r=1;
  for i,j in zip(s[::2],s[1::2]):r*=int(i)**int(j);s=str(r);
 return o[-1]

Ungoldfed

def f(s):
 o=[['1',s]['-'in s]]
 while s not in o:
  o+=[s]
  s+='1'*(len(s)%2==1)
  r=1
  for i,j in zip(s[::2],s[1::2]):
   r*=int(i)**int(j)
  s=str(r)
 return o[-1]

Results

>>> [f(i) for i in ['135', '1234', '642', '2592', '-15']]
['5', '8', '2592', '2592', '-15']
share|improve this answer
    
@PeterTaylor Fixed! – Erwan Mar 8 at 13:44
    
You can put multiple statements in one line if you seperate them with a ; This way you saves you the intendation whitespaces. Also you can put the body of the for loop on that same line. – DenkerAffe Mar 10 at 9:17
    
Suggested golfing:def f(s,o=[['1',s]["-"in s]],n=int): while s not in o: o+=[s];s+=1*(len(s)%2<1);r=1 for i,j in zip(s[::2],s[1::2]):r*=n(i)**n(j) s=str(r) return o[-1] – CalculatorFeline Mar 10 at 17:26
    
@CatsAreFluffy o=[['1',s]["-"in s]] in default argument don't work for me it raise a error ` s not defined` – Erwan Mar 11 at 6:58
    
Oops, move o to the next line. – CalculatorFeline Mar 11 at 14:32

Oracle SQL 11.2, 456 bytes

WITH v(n,c,i,f,t)AS(SELECT:1+0,CEIL(LENGTH(:1)/2),1,'1',0 FROM DUAL UNION ALL SELECT DECODE(SIGN(c-i+1),-1,t,n),DECODE(SIGN(c-i+1),-1,CEIL(LENGTH(t)/2),c),DECODE(SIGN(c-i+1),-1,1,i+1),DECODE(SIGN(c-i+1),-1,'1',RTRIM(f||'*'||NVL(POWER(SUBSTR(n,i*2-1,1),SUBSTR(n,i*2,1)),SUBSTR(n,i*2-1,1)),'*')),DECODE(SIGN(c-i+1),-1,0,TO_NUMBER(column_value))FROM v,XMLTABLE(f)WHERE i<=c+2 AND:1>9)CYCLE n,c,i,f,t SET s TO 1 DEFAULT 0SELECT NVL(SUM(n),:1) FROM v WHERE s=1;

Un-golfed

WITH v(n,c,i,f,t) AS
(
  SELECT :1+0,CEIL(LENGTH(:1)/2),1,'1',0 FROM DUAL
  UNION ALL
  SELECT DECODE(SIGN(c-i+1),-1,t,n),
         DECODE(SIGN(c-i+1),-1,CEIL(LENGTH(t)/2),c),
         DECODE(SIGN(c-i+1),-1,1,i+1),
         DECODE(SIGN(c-i+1),-1,'1',RTRIM(f||'*'||NVL(POWER(SUBSTR(n,i*2-1,1),SUBSTR(n,i*2,1)),SUBSTR(n,i*2-1,1)),'*')),
         DECODE(SIGN(c-i+1),-1,0,TO_NUMBER(column_value))
  FROM v,XMLTABLE(f) WHERE i<=c+2 AND :1>9 
)  
CYCLE n,c,i,f,t SET s TO 1 DEFAULT 0
SELECT NVL(SUM(n),:1) FROM v WHERE s=1;

v is a recursive view, parameters are

n : number to split in 2 digits parts

c : number of 2 digits parts

i : current 2 digits part to compute

f : string concatenating the powers with * as separator

t : evaluation of f

The DECODEs switch to the next number to split and compute when all the parts of the current number are done.

XMLTABLE(f) takes an expression an evaluates it, putting the result in the pseudo column "column_value". It's the golfed version of http://tkyte.blogspot.fr/2010/04/evaluating-expression-like-calculator.html

CYCLE is the oracle build in cycle detection and is used as the exit condition.

Since the result for :1<10 is :1 and v returns no row for those cases, SUM forces a row with NULL as the value. NVL returns :1 as the result if the row is null.

share|improve this answer
    
Where's the explanation? – DerpfacePython Mar 11 at 23:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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