11
\$\begingroup\$

Given is any integer x > 0 and any base y > 3.

  1. Sum all digits of x (if written in the set base).
  2. Multiply this by the highest possible digit (is always base -1).
  3. Repeat until this value is (y - 1) ^ 2

Searched is the count of iterations and the steps.

Example 1:

x= 739
y= 7
searched: (7 - 1) ^ 2 = 36

based: (b7)2104
sum: (dec)7
mul: (dec)42

based: (b7)60
sum: (dec)6
mul: (dec)36

2 steps needed -> answer is [2, 739, 42, 36] or [739, 42, 36, 2]

Example 2:

x = 1712
y = 19
s: 324

step1: 1712 -> 360
step2:  360 -> 648
step3:  648 -> 324

3 steps needed -> answer is [3, 1712, 360, 648, 324] or [1712, 360, 648, 324, 3]

Special:
In some cases (some combinations with a base of 3) you will not be able to get to (y - 1) ^ 2 like for x = 53 and y = 3. For this reason y needs to be bigger than 3 and you can ignore this.

The count of iterations need to be the first or the last value

This is lowest byte-count wins.

\$\endgroup\$
2
  • \$\begingroup\$ Requiring the number of steps in the answer seems like an unnecessary addition to the problem. My solution had to add 21 bytes to do what amounted to finding the length of a list and subtracting 1. \$\endgroup\$
    – user61980
    Dec 11, 2016 at 22:32
  • \$\begingroup\$ @ngenisis going with just an order of the output, but ignoring the method (array, stack, delim. string, multiple strings....). To keep track of 2 different things (final value and count) avoids the "blind" collecting of values (more or less) and is a good addition to my eye. Maybe a different approach will need 5 more bytes at the calculation but saves 8 at the counting part (just random numbers here). \$\endgroup\$ Dec 11, 2016 at 23:32

7 Answers 7

4
\$\begingroup\$

Jelly, 14 13 bytes

-1 byte by printing as it loops ( replacing a chain separation, µ and concatenation ;)

Ṅb⁹S×⁹’¤µÐĿL’

TryItOnline!

How?

Ṅb⁹S×⁹’¤µÐĿL’ - Main link: x, y
        µÐĿ   - loop monadically until results are no longer unique and collect
Ṅ             - print z (initially x), then result of previous loop and return z
  ⁹           -     right argument (y, even though monadic)
 b            -     left to base right
   S          -     sum (the result was a list of base y digits)
       ¤      -     nilad followed by link(s) as a nilad
     ⁹’       -         y decremented
    ×         -     multiply
           L  - length(z)
            ’ - decrement
              - implicit print

The alternative 13 byter prints each input to the loop plus a line feed (), and finally implicitly prints the decremented count of the collected results, removing the need for a monadic chain separation (µ) and concatenation (;).

\$\endgroup\$
2
  • 1
    \$\begingroup\$ As there is no set "output formatting" requested. Multiple outputs will count as long as the order is fine. This way, the 13 byte answer is valid. \$\endgroup\$ Dec 11, 2016 at 23:37
  • \$\begingroup\$ Cool, I was not certain, thanks for letting me know! \$\endgroup\$ Dec 12, 2016 at 15:09
4
\$\begingroup\$

Perl 6, 60 bytes

{$/=[$^x,*.polymod($^y xx*).sum*($y-1)...($y-1)²];$/-1,|$/}

Expanded:

{    # bare block lambda with placeholder parameters 「$x」 「$y」

  $/ = [          # store in 「$/」 ( so that we don't have to declare it )

    # generate a sequence

    $^x,          # declare first parameter, and seed sequence generator

    # Whatever lambda

    *\            # the parameter to this lambda

    .polymod(     # broken down with a list of moduli

      $^y         # declare second parameter of the outer block lambda
      xx *        # an infinite list of copies of it

    )
    .sum
    *
    ( $y - 1 )

    # end of Whatever lambda

    ...           # repeat until it reaches

    ( $y - 1 )²
  ];

  # returns
  $/ - 1,         # count of values minus one
  |$/             # Slip 「|」 the list into the result
}

Usage:

# store it in the lexical namespace so that it is easier to understand
my &code = {$/=[$^x,*.polymod($^y xx*).sum*($y-1)...($y-1)²];$/-1,|$/}

say code  739,  7; # (2 739 42 36)
say code 1712, 19; # (3 1712 360 648 324)
\$\endgroup\$
4
\$\begingroup\$

C, 116 113 bytes

-3 bytes for recalculating square each time

s,t,i;f(x,y){s=y-(i=1);while(x-s*s){t=0;++i;printf("%d ",x);while(x)t+=x%y,x/=y;x=t*y-t;}printf("%d %d ",x,i-1);}

Ungolfed and usage:

s,t,i;
f(x,y){
 s=y-(i=1);
 while(x-s*s){
  t=0;
  ++i;
  printf("%d ",x);
  while(x)
   t+=x%y,    //add the base y digit
   x/=y;      //shift x to the right by base y
  x=t*y-t;
 }
 printf("%d %d ",x,i-1);
}

main(){
 f(739,7);puts("");
 f(1712,19);puts("");
}
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 97 91 84 82 bytes

f=(n,b,k=1,c=b-1)=>[n,(s=(B=n=>n%b*c+(n>b&&B(n/b|0)))(n))-c*c?f(s,b,k+1):[s,k]]+''

Test cases

f=(n,b,k=1,c=b-1)=>[n,(s=(B=n=>n%b*c+(n>b&&B(n/b|0)))(n))-c*c?f(s,b,k+1):[s,k]]+''

console.log(f(1712, 19))
console.log(f(739, 7))

\$\endgroup\$
4
\$\begingroup\$

Jelly, 16 bytes

I guess I'll post this anyway, even though it was beaten while I was writing it, because it's a notably different algorithm and it was interesting to write. (I couldn't figure out how ÐĿ parsed from the docs and had to give up on it, despite knowing it would probably lead to a shorter solution than this one.)

ṄbS×⁹’¤ß<’¥n⁸$?‘

Try it online!

Explanation:

ṄbS×⁹’¤ß<’¥n⁸$?‘
Ṅ                 Output {the first argument} and a newline
 b                Convert to base {the second argument}
  S               Sum digits
    ⁹’¤           {the second argument} minus 1, parsed as a group
   ×              Multiply
           n⁸$    {the current value} ≠ {the first argument}, parsed as a group
              ?   If that's true:
       ß          then run the whole program recursively
        <’¥       else run (lambda a,b: (a<b)-1)
               ‘  Increment the result

The use of <’¥ is basically a short way to write a dyad (link with two arguments) that always returns -1 (because we know the answer will never be smaller than the base). Choosing between running that recursively, and the whole program recursively, lets us determine when to stop looping. Then when the stack unwinds at the end of the recursion, we keep incrementing the -1 to determine how many steps there were.

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

MATL, 25 21 bytes

4 bytes saved thanks to @Luis

XJx`tJYA!UsJq*tJqU-}@

Try it Online!

Explanation

XJ      % Implicitly grab the first input and store in clipboard J
x       % Delete this from the stack
`       % Do...while loop
  t     % Duplicate last element on stack (implicitly grabs second input)
  JYA   % Convert this number to the specified base
  !Us   % Sum the digits
  Jq*   % Multiply by the largest number in this base
  t     % Duplicate this value
  JqU   % Compute (base - 1) ^ 2
  -     % Subtract the two. Evaluates to TRUE if they are not equal
}       % When they are finally equal
@       % Push the number of iterations
        % Implicitly display the stack contents
\$\endgroup\$
1
  • \$\begingroup\$ @LuisMendo Fixed! \$\endgroup\$
    – Suever
    Dec 11, 2016 at 21:56
1
\$\begingroup\$

Mathematica, 80 bytes

(s=FixedPointList[x(#2-1)(Plus@@x~IntegerDigits~#2),#];s[[-1]]=Length@s-2;s)&

is the private use character U+F4A1 used to represent \[Function]. If the number of steps weren't required in the answer, this could be done in 60 bytes:

Most@FixedPointList[x(#2-1)(Plus@@x~IntegerDigits~#2),#]&
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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