Jumlahkan digit sampai Square

11

Diberikan adalah bilangan bulat x> 0 dan basis apa saja y> 3.

  1. Jumlahkan semua digit x (jika ditulis dalam basis yang ditetapkan).
  2. Lipat gandakan ini dengan digit setinggi mungkin (selalu base -1).
  3. Ulangi sampai nilai ini (y - 1) ^ 2

Yang dicari adalah hitungan iterasi dan langkah-langkahnya.

Contoh 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]

Contoh 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]

Khusus:
Dalam beberapa kasus (beberapa kombinasi dengan basis 3) Anda tidak akan bisa (y - 1) ^ 2menyukai untuk x = 53dan y = 3. Untuk alasan ini yharus lebih besar dari 3 dan Anda dapat mengabaikannya.

Hitungan iterasi harus menjadi nilai pertama atau terakhir

Ini adalah kemenangan byte-count terendah.

Dirk Reichel
sumber
Membutuhkan sejumlah langkah dalam jawaban sepertinya merupakan tambahan yang tidak perlu untuk masalah tersebut . Solusi saya harus menambahkan 21 byte untuk melakukan apa yang sama dengan menemukan panjang daftar dan mengurangi 1.
ngenisis
@ngenis hanya berjalan dengan urutan output, tetapi mengabaikan metode (array, stack, delim. string, multiple strings ....). Untuk melacak 2 hal yang berbeda (nilai dan penghitungan akhir), hindari pengumpulan nilai "buta" (kurang lebih) dan merupakan tambahan yang bagus untuk mata saya. Mungkin pendekatan yang berbeda akan membutuhkan 5 byte lebih pada perhitungan tetapi menyimpan 8 pada bagian penghitungan (hanya angka acak di sini).
Dirk Reichel

Jawaban:

4

Jelly , 14 13 byte

-1 byte dengan mencetak saat loop ( menggantikan pemisahan rantai, µdan penggabungan ;)

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

TryItOnline!

Bagaimana?

Ṅ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

Byter 13 alternatif mencetak setiap input ke loop plus feed baris ( ), dan akhirnya secara implisit mencetak jumlah yang dikurangi dari hasil yang dikumpulkan, menghilangkan kebutuhan untuk pemisahan rantai monadik ( µ) dan concatenation ( ;).

Jonathan Allan
sumber
1
Karena tidak ada set "output format" yang diminta. Banyak output akan dihitung selama pesanan baik-baik saja. Dengan cara ini, jawaban 13 byte valid.
Dirk Reichel
Keren, saya tidak yakin, terima kasih sudah memberi tahu saya!
Jonathan Allan
4

Perl 6 , 60 byte

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

Diperluas:

{    # 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
}

Pemakaian:

# 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)
Brad Gilbert b2gills
sumber
4

C, 116 113 byte

-3 byte untuk menghitung ulang kuadrat setiap kali

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);}

Tidak digabungkan dan digunakan:

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("");
}
Karl Napf
sumber
4

JavaScript (ES6), 97 91 84 82 byte

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]]+''

Uji kasus

Arnauld
sumber
4

Jelly , 16 byte

Saya kira saya tetap akan memposting ini, meskipun sudah dikalahkan saat saya menulisnya, karena ini adalah algoritma yang sangat berbeda dan menarik untuk ditulis. (Saya tidak tahu bagaimana ÐĿparsing dari dokumen dan harus menyerah, meskipun tahu itu mungkin akan mengarah ke solusi yang lebih pendek daripada yang ini.)

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

Cobalah online!

Penjelasan:

Ṅ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

Penggunaan <’¥pada dasarnya adalah cara singkat untuk menulis angka dua (tautan dengan dua argumen) yang selalu mengembalikan -1 (karena kita tahu jawabannya tidak akan pernah lebih kecil dari basis). Memilih antara menjalankan itu secara rekursif, dan seluruh program secara rekursif, memungkinkan kami menentukan kapan harus berhenti mengulang. Kemudian ketika tumpukan dibuka di akhir rekursi, kami terus menambah -1 untuk menentukan berapa banyak langkah yang ada.


sumber
2

MATL, 25 21 byte

4 byte disimpan berkat @Luis

XJx`tJYA!UsJq*tJqU-}@

Cobalah secara Online!

Penjelasan

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
Suever
sumber
@LuisMendo Diperbaiki!
Suever
1

Mathematica, 80 byte

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

adalah karakter penggunaan pribadi yang U+F4A1digunakan untuk mewakili \[Function]. Jika jumlah langkah tidak diperlukan dalam jawaban, ini bisa dilakukan dalam 60 byte:

Most@FixedPointList[x(#2-1)(Plus@@x~IntegerDigits~#2),#]&
ngenisis
sumber