18
\$\begingroup\$

Kuznetsov's Sequence

(I made the name up, don't bother with Wikipedia or Google)

Given any number n > 0, let r represent the reverse of the number n. Iterate until the final result is zero, passing the result of each iteration back into the function using recursion or a methodology of your choice by performing the below operation:

  • If r > n for that iteration the result is r % n.
  • If n > r for that iteration the result is n % r.
  • If n % r = 0 or r % n = 0, you terminate iteration.

Take the intermediate result of each execution and store them in an array for the final answer. The initial number n is not part of the sequence, nor is 0; the examples should make everything a little more obvious.

Lets walk through an example where n=32452345.

54325423 % 32452345 = 21873078 # r > n, uses r % n
87037812 % 21873078 = 21418578 # r > n, uses r % n
87581412 % 21418578 = 1907100  # r > n, uses r % n
1907100 % 17091 = 9999         # n > r, uses n % r
9999 % 9999 = 0                # r % n = n % r = 0, terminated

Result: [21873078, 21418578, 1907100, 9999]     

Another example n=12345678:

87654321 % 12345678 = 1234575 # r > n, uses r % n
5754321 % 1234575 = 816021    # r > n, uses r % n
816021 % 120618 = 92313       # n > r, uses n % r
92313 % 31329 = 29655         # n > r, uses n % r
55692 % 29655 = 26037         # r > n, uses r % n
73062 % 26037 = 20988         # r > n, uses r % n
88902 % 20988 = 4950          # r > n, uses r % n
4950 % 594 = 198              # n > r, uses n % r
891 % 198 = 99                # r > n, uses r % n
99 % 99 = 0                   # r % n = n % r = 0, terminated

Result: [1234575, 816021, 92313, 29655, 26037, 20988, 4950, 198, 99]

A final example n=11000:

11000 % 11 = 0 # n % r = 0, terminated

Result: []

This is lowest byte-count wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ Can the results be printed as the calculations happen or must it construct an array? \$\endgroup\$ – FlipTack Dec 9 '16 at 21:35
  • \$\begingroup\$ I'd assume the default output rules apply, so you can choose output formart (array, displayed numbers separated by spaces, ...) \$\endgroup\$ – Luis Mendo Dec 9 '16 at 21:43
  • \$\begingroup\$ @Flp.Tkc I will not restrict output, as long as the numbers required are displayed. \$\endgroup\$ – Magic Octopus Urn Dec 9 '16 at 21:47
  • 2
    \$\begingroup\$ Just a note that the 'reverse' of a number is only meaningful with respect to a particular base. \$\endgroup\$ – David Conrad Dec 10 '16 at 6:49
  • 1
    \$\begingroup\$ @Sp3000 sort of; except that you need to take the reverse every iteration. You only thread one number through the calculation, not two, and take the second to always be the reverse of the first. \$\endgroup\$ – tomsmeding Dec 10 '16 at 9:50

16 Answers 16

4
\$\begingroup\$

05AB1E, 11 bytes

[‚{R`%Ð>#,

Uses the CP-1252 encoding. Try it online!

\$\endgroup\$
6
\$\begingroup\$

PowerShell v2+, 89 bytes

param($n)for(){$r=-join"$n"["$n".length..0];if(!($n=(($r%$n),($n%$r))[$n-gt$r])){exit}$n}

Iterative solution. Lengthy because there's no easy way to reverse an array, so we stringify it and index on it backwards to store into $r. Then a pseudo-ternary to pull out the appropriate modulo and re-store into $n for the next round. However, if the result is zero, that means the !($n...) will be $true, so we exit instead of $n. The numbers are left on the pipeline and (implicitly) returned as an array, but without an encapsulating pipeline or saving the results into a variable, the default Write-Output sticks a newline between.

Try it online! (Yes, dead serious.)
PowerShell is now on TIO! You gotta give it a second or two, because PowerShell is a beast to startup, but now you, yes you, can verify PowerShell code right in your browser!

\$\endgroup\$
  • \$\begingroup\$ Gah, beat me to it and with the same approach. Nice! \$\endgroup\$ – briantist Dec 9 '16 at 22:01
6
\$\begingroup\$

Perl, 43 38 + 1 = 39 bytes

Run with the -n flag

say while$_=($;=reverse)>$_?$;%$_:$_%$

Try it online! Includes the two non-empty examples.

Explanation chart

-n: Wraps the entire program in while(<>){ ... ;}. This turns the above code into the following line: while(<>){say while$_=($;=reverse)>$_?$;%$_:$_%$;}. Notice, a semicolon has been added to the trailing $, so it now becomes an instance of the variable $;. In the condition of a while loop, <> automatically reads one line of input and saves it in the $_ variable. So now let's look at what the interpreter reads inside the outer while loop:

say while$_=($;=reverse)>$_?$;%$_:$_%$;
[op][mod][         condition          ]     #While is acting as a statement modifier.
                                            #It evaluates the operation as long as the condition is truthy.
            ($;=reverse)>$_?$;%$_:$_%$;     #The meat of the program: a ternary operation
            ($;=reverse)                    #The reverse function takes $_ as a parameter by default, and reverses the value.
                                            #The value returned by reverse is stored in the variable $;
                        >$_                 #A condition asking if $% is greater than $_.  Condition of the ternary operation
                           ?$;%$_           #If true, then return $; modulo $_
                                 :$_%$;     #If false, return $_ modulo $;
         $_=                                #Assign the result of the ternary operation back into $_
                                            #If $_ is non-zero, then the condition is true, and while will evaluate the operation
say                                         #Implicitly takes the $_ variable as parameter, and outputs its contents

Original code, saved for posterity: 43 + 1 = 44 bytes

say$_=$%>$_?$%%$_:$_%$%while$_-($%=reverse)
\$\endgroup\$
  • \$\begingroup\$ $%>$_?$%%$_:$_%$% Did you choose the $% variable on purpose just for this line? \$\endgroup\$ – tomsmeding Dec 10 '16 at 9:53
  • \$\begingroup\$ Almost - I also save 1 byte by using a non-alphanumeric character for the last character before the while statement, so I don't need a whitespace. Other than that - pretty much, yeah \$\endgroup\$ – Gabriel Benamy Dec 10 '16 at 10:22
5
\$\begingroup\$

Pyth, 13 12 bytes

t.u|%F_S,s_`

Thanks to @TheBikingViking.

Try it online: Demonstration

My old code:

W
W=Q%F_S,s_`

Try it online: Demonstration

Explanation:

t.u|%F_S,s_`NNNQ  implicit Ns and Q at the end
               Q  start with N = Q (Q = input number)
        ,         create a pair with the numbers
         s_`N        convert N to string -> reverse-> convert to int
             N       and N
       S          sort
      _           reverse
    %F            fold by modulo
   |          N   or N (if the result is zero use N instead to stop)
 .u               apply this ^ procedure until a value repeats
                  print all intermediate values
 t                except the first one (the original number)
\$\endgroup\$
  • \$\begingroup\$ 12 bytes: t.u|%F_S,s_<backtick>. Test \$\endgroup\$ – TheBikingViking Dec 9 '16 at 22:40
  • 1
    \$\begingroup\$ @TheBikingViking Thanks, that is really clever. \$\endgroup\$ – Jakube Dec 9 '16 at 23:05
4
\$\begingroup\$

Jelly, 15 14 13 bytes

,ṚḌṢṚ%/
ÇÇпḊ

TryItOnline

How?

,ṚḌṢṚ%/ - Link 1, iterative procedure: n
,       - pair n with
 Ṛ      - reverse n
  Ḍ     - undecimal (int of digit list)
   Ṣ    - sort
    Ṛ   - reverse
     %/ - reduce with mod

ÇÇпḊ - Main link: n
  п  - collect while
 Ç    - last link as a monad is truthy
Ç     -     last link as a monad
    Ḋ - dequeue (remove the input from the head of the resulting list)
\$\endgroup\$
4
\$\begingroup\$

Jelly, 13 12 bytes

,ṚḌṢṚ%/Ṅß$Ṡ¡

This is a monadic link/function that prints to STDOUT.

Try it online!

How it works

,ṚḌṢṚ%/Ṅß$Ṡ¡  Monadic link. Argument: n

,Ṛ            Pair n and its reversed digit list.
  Ḍ           Convert the digit list into an integer.
   ṢṚ         Sort and reverse.
     %/       Reduce by modulo. Result: m
          Ṡ¡  Do sign(m) times:
       Ṅß$    Print with a newline and call the link recursively.
\$\endgroup\$
  • \$\begingroup\$ What's the footer for? If removed the code seems to output a trailing 0 \$\endgroup\$ – Luis Mendo Dec 9 '16 at 21:46
  • \$\begingroup\$ That's correct. The 0 is the return value of the function, which the interpreter prints if it isn't discarded. As per this meta discussion, that's allowed. \$\endgroup\$ – Dennis Dec 9 '16 at 21:46
4
\$\begingroup\$

Python 2, 92 87 81 73 61 bytes

Recursive solution:

def f(n):
    r=int(`n`[::-1]);x=min(r%n,n%r)
    if x:print x;f(x)

Try it online

Iterative solution: (also 61 bytes)

n=input()
while n:r=int(`n`[::-1]);n=min(r%n,n%r);print n/n*n

Try it online

\$\endgroup\$
  • \$\begingroup\$ The iterative solution that i gave you is actually 59 bytes, but I'm not sure if it's valid because it prints the input. If it is, then you can golf of 2 bytes by just doing while n:. Otherwise, you can do it with 61 bytes. \$\endgroup\$ – FlipTack Dec 9 '16 at 22:32
3
\$\begingroup\$

MATL, 16 bytes

`tVPUhSPZ}\tt]xx

Try it online!

Explanation

`         % Do...while
  t       %   Duplicate. Takes input implicitly in the first iteration
  VPU     %   Transform the number at the top of the stack by reversing its digits
  hSPZ}   %   Concatenate the two numbers into an array, sort, reverse, split the
          %   array: this moves the smaller number to the top
  \       %   Modulo
  t       %   Duplicate. The original copy is left on the stack for displaying, 
          %   and the duplicate will be used for computing the next number
  t       %   Duplicate. This copy will be used as loop condition: exit if 0
]         % End
xx        % Delete the two zeros at the top. Implicitly display rest of the stack
\$\endgroup\$
2
\$\begingroup\$

PHP, 78 bytes

function a($n){while(($r=strrev($n))&&($n=$r>$n?$r%$n:$n%$r)!=0){echo$n.' ';}}
\$\endgroup\$
2
\$\begingroup\$

Batch, 140 bytes

@echo off
set/pn=
:l
set/am=n,l=0
:r
set/al=l*10+m%%10,m/=10
if %m% gtr 0 goto r
set/an=l%%n%%l+n%%l%%n
if %n% gtr 0 echo %n%&goto l

Takes input on STDIN and outputs the sequence on separate lines. Batch has conditional statements (which are somewhat verbose) but no conditional expressions so it's easier (despite having to quote the %s) to compute r%n%r (which is equal to r%n if n<r or zero if n>r) and n%r%n (which is equal to n%r if n>r or zero if n<r) and add them together.

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

Mathematica, 68 bytes

Thanks to Greg Martin for suggesting I use FixedPointList rather than NestWhileList:

FixedPointList[Mod[(r=IntegerReverse@#)~Max~#,r~Min~#]&,#][[2;;-4]]&

The shortest I could get my original solution with FixedPointList was 73 bytes:

NestWhileList[Mod[(r=IntegerReverse@#)~Max~#,r~Min~#]&,#,#!=0&][[2;;-2]]&
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that you don't have quite the right terminating condition (try the example input 11000). You might get around this by switching to the technique described in your last paragraph. But I don't see how to get rid of Rest or Most in this way. On the other hand, FixedPointList[ Mod[(r = IntegerReverse@#)~Max~#, r~Min~#] &, #][[2 ;; -4]] & is only 68 bytes once the spaces are removed (throws a couple of errors, nbd). \$\endgroup\$ – Greg Martin Dec 10 '16 at 2:30
  • \$\begingroup\$ I had somehow convinced myself that spans like {a,b,c,d}[[2;;-4]] would give an error rather than the empty list (I probably used a comma rather than ;;). Learned something. \$\endgroup\$ – ngenisis Dec 10 '16 at 2:51
  • \$\begingroup\$ You can get rid of that whole min/max business with a Sort: FixedPointList[-Mod@@Sort@-{#,IntegerReverse@#}&,#][[2;;-4]]& \$\endgroup\$ – Martin Ender Dec 10 '16 at 11:45
1
\$\begingroup\$

JavaScript, 72 70 bytes

f=(s,...o)=>(u=s>(z=[...s+''].reverse().join``)?s%z:z%s)?f(u,...o,u):o

console.log(...[32452345, 12345678, 11000].map(x=>f(x)))
.as-console-wrapper{max-height:100%!important}

Edited:

-2 bytes: Spread operator waits string concatenation.

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

R, 126 117 bytes

x=scan();while(x){y=sort(c(x,as.double(paste(rev(el(strsplit(c(x,""),""))),collapse=""))));if(x<-y[2]%%y[1])print(x)}

Sadly, reversing a number (as.double(paste(rev(el(strsplit(c(x,""),""))),collapse="")))) is pretty wordy. Rest is pretty easy. Uses sort to indirectly check which is higher.

The rest is straightforward, it keeps looping until x=0, and prints all steps.

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

C, 87 bytes

t;r;f(n){while(t=n){r=0;while(t)r=10*r+t%10,t/=10;n=r>n?r%n:n%r;if(n)printf("%d ",n);}}

t is temporary for reversing. The inner loop shifts r 1 digit to the left and adds the last digit of t until it is exhausted. Output is after the first iteration and only if it is non-zero to prevent the first and last item to be displayed.

Ungolfed and usage:

t;r;
f(n){
  while (t = n){
    r = 0;
    while (t)
      r = 10*r + t%10,
      t /= 10; 
    n = r>n ? r%n : n%r;
    if(n)
      printf("%d ",n);
  }
}
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 64 bytes

NestWhileList[#2~If[#<=#2,Mod,#0]~#&[IntegerReverse@#,#]&,#,#>0&]&

The above code represents a pure function which takes a single input, and returns the kuznetsovs sequence. The really beautiful thing about mathematica is that you can put layer upon layer of pure functions... Allow me to explain the code ;)

Each term in the sequence itself is calculated with the below function, which takes one input and returns the next term.

#2~If[#<=#2,Mod,#0]~#&[IntegerReverse@#,#]&

The code IntegerReverse@# just generates r, the reversed value. The code #2~If[#<=#2,Mod,#0]~#& is a function that takes two inputs and either does the mod operation, or reverses the inputs and calls itself again. Another way of writing it is If[#<=#2, Mod, #0][#2, #]&, or it could be written as a regular function like this: k[a_, b_] := If[a <= b, Mod, k][b, a]

\$\endgroup\$
0
\$\begingroup\$

Racket 180 bytes

(let p((n n)(ol'()))(let*((v reverse)(o modulo)
(r(string->number(list->string(v(string->list(number->string n))))))
(m(if(> n r)(o n r)(o r n))))(if(= m 0)(v ol)(p m(cons m ol)))))

Ungolfed:

(define (f n)
  (let loop ((n n)
             (ol '()))
    (let* ((r (string->number
               (list->string
                (reverse
                 (string->list
                  (number->string n))))))
           (m (if (> n r)
                  (modulo n r)
                  (modulo r n))))
      (if (= m 0)
          (reverse ol)
          (loop m (cons m ol))))))

Testing:

(f 32452345)
(f 12345678)

Ouput:

'(21873078 21418578 1907100 9999)
'(1234575 816021 92313 29655 26037 20988 4950 198 99)
\$\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.