22
\$\begingroup\$

Given an integer n > 2, print or return the smallest non-negative integer k such that a(n, k) = 9, where a(n, k) is defined by:

  • a(n, 0) = n
  • a(n, k+1) =
    • a(n, k) / 2 + 1 if a(n, k) is even
    • the sum of the digits of a(n, k)² (in base 10) if a(n, k) is odd

Examples

For n = 5, the expected output is k = 4:

a(5, 0) = 5
a(5, 1) = 7  (5² = 25 and 2 + 5 = 7)
a(5, 2) = 13 (7² = 49 and 4 + 9 = 13)
a(5, 3) = 16 (13² = 169 and 1 + 6 + 9 = 16)
a(5, 4) = 9  (16 / 2 + 1)

For n = 40, the expected output is k = 2:

a(40, 0) = 40
a(40, 1) = 21 (40 / 2 + 1)
a(40, 2) = 9  (21² = 441 and 4 + 4 + 1 = 9)

Clarifications and rules

  • The input is guaranteed to be greater than 2.
  • Your program should theoretically work for any value of n. (In practice, it may be limited by the maximum integer size supported by your language.)
  • k may be either 0-indexed or 1-indexed. Please state it in your answer.
  • This is , so the shortest answer in bytes wins!

First values

Below are the first values from n = 3 to n = 422, with k 0-indexed. (For 1-indexing, just add 1 to these values.)

 1  2  4  3  3  5  0  4  3  4  2  6  1  1  6  5  5  4  1  5  2  3  3  7  6  2  3  2  2  7
 6  6  5  6  6  5  1  2  2  6  6  3  1  4  3  4  4  8  1  7  6  3  5  4  6  3  2  3  3  8
 7  7  3  7  4  6  6  7  5  7  6  6  6  2  4  3  3  3  6  7  3  7  2  4  7  2  6  5  6  4
 7  5  2  5  6  9  6  2  3  8  2  7  1  4  6  6  6  5  1  7  4  4  3  3  7  4  3  4  2  9
 6  8  6  8  6  4  6  8  2  5  3  7  6  7  3  8  2  6  7  8  6  7  5  7  6  7  4  3  3  5
 6  4  3  4  4  4  6  7  6  8  3  4  6  8  7  3  6  5  6  8  3  3  2  7  6  6  5  7  6  5
 7  8  2  6  3  3  6  6  6  7  4 10  6  7  3  3  6  4  1  9  2  3  3  8  7  2  6  5  2  7
 7  7  6  7  3  6  7  2  4  8  3  5  6  5  6  4  2  4  6  8  3  5  6  4  7  5  2  3  6 10
 7  7  3  9  2  7  1  9  5  7  6  5  6  7  4  9  6  3  6  6  3  4  2  8  7  7  6  8  6  4
 7  9  4  3  3  7  7  8  3  9  4  7  6  8  3  6  6  8  7  7  7  8  6  5  7  4  6  4  2  6
 7  7  6  5  3  4  7  5  4  5  3  5  7  7  6  8  2  7  1  9  6  4  6  5  7  7  2  9  6  8
 7  4  3  7  4  6  6  7  6  9  3  4  6  4  2  3  3  8  1  7  6  7  2  6  7  8  3  7  5  6
 7  8  2  9  3  3  6  7  6  4  4  4  6  7  6  7  6  7  6  8  7  5  6 11  7  7  3  8  4  4
 7  4  6  7  3  5  6  2  2 10  6  3  6  4  3  4  4  9  7  8  3  3  6  7  7  6  4  3  6  8
\$\endgroup\$
9
  • 23
    \$\begingroup\$ Obligatory nitpick on the title: 9! ≠ 9 \$\endgroup\$ – JungHwan Min Sep 6 '17 at 2:03
  • 1
    \$\begingroup\$ Cool sequence. Did you discover this yourself? \$\endgroup\$ – Robert Fraser Sep 6 '17 at 4:37
  • \$\begingroup\$ @RobertFraser I did, but I'm sure similar sequences exist somewhere (I couldn't find one, but I didn't spend much time searching.) \$\endgroup\$ – Arnauld Sep 6 '17 at 9:42
  • \$\begingroup\$ After Collatz conjecture, Arnauld's Conjecture! What's next? \$\endgroup\$ – sergiol Sep 6 '17 at 10:56
  • \$\begingroup\$ @sergiol According to lmgtfy.com/?q=conjecture a conjecture is an opinion or conclusion formed on the basis of incomplete information. \$\endgroup\$ – Roman Gräf Sep 6 '17 at 16:42

17 Answers 17

6
\$\begingroup\$

Husk, 13 bytes

€9¡?o→½ȯΣd□¦2

This is 1-indexed. Try it online!

Explanation

Nothing too fancy here.

€9¡?o→½ȯΣd□¦2  Implicit input, say n = 5
  ¡            Iterate the following function:
   ?       ¦2   If divisible by 2,
    o→½         then halve and increment,
       ȯΣd□     else square, take digits and get their sum.
               This gives an infinite sequence: [5,7,13,16,9,9,9,9,9..
€9             1-based index of 9; print implicitly.
\$\endgroup\$
1
  • \$\begingroup\$ I think it would be nice if solved this. \$\endgroup\$ – H.PWiz Sep 6 '17 at 11:21
10
\$\begingroup\$

Perl 6, 41 bytes (40 chars)

{+($_,{$_%2??[+] $_².comb!!$_/2+1}...9)}

Try it online!

This uses 1-indexing of k's, so it gives 1 higher answers than the examples in OP. If this is not what the 1-indexing means, I'll have to add 1 byte more.

Explanation: It's an anonymous function. We just use the Perl 6's facility for generating lists using recursion :—). It looks like this: (first element),(block that takes the previous element and gives the next)...(end condition). In this case, the first element is $_ (argument of the main function) and the end condition is 9 (fulfilled when we generate a 9). In the middle block, we use $_ to refer to its argument ( = the previous element of the sequence). The ?? !! is the old ternary operator (better known as ? :). Finally, we take the length of this list by forcing numerical context by +(...).

The last weird thing here is the sum of digits. Numbers are Cool (behave both like strings and numbers), so we use a string method .comb on $_² (give list of characters = digits), then adding the characters up (that converts them back to numbers).

\$\endgroup\$
1
  • \$\begingroup\$ Yes, this is what 1-indexing means. \$\endgroup\$ – Arnauld Sep 5 '17 at 22:25
7
\$\begingroup\$

Jelly, 17 bytes

²DSµH‘$Ḃ?ßµ-n9$?‘

Try it online!

Straight-forward approach. Uses 0-based indexing.

Explanation

²DSµH‘$Ḃ?ßµ-n9$?‘  Input: n
               ?   If
            n9$      n != 9
          µ        Then
        ?            If
       Ḃ               n % 2 == 1
   µ                 Then
²                      Square
 D                     Decimal digits
  S                    Sum
      $              Else
    H                  Halve
     ‘                 Increment
         ß           Call recursively
                   Else
           -         The constant -1
                ‘  Increment
\$\endgroup\$
1
  • 1
    \$\begingroup\$ @Arnauld Thanks, the conditional was a do-while n != 9 instead of a while n!= 9 \$\endgroup\$ – miles Sep 5 '17 at 23:43
7
\$\begingroup\$

Python 2, 129 126 76 68 67 64 54 53 bytes

-3 bytes thanks to Jonathan Frech. -8 bytes thanks to Maltysen. -7 bytes thanks to Jonathan Allan. -1 byte thanks to Mr. Xcoder.

f=lambda n:n-9and-~f(n%2*sum(map(int,`n*n`))or 1+n/2)

Try it online!

From somebody who probably doesn't know enough math, this seems completely arbitrary. :P

\$\endgroup\$
6
  • 1
    \$\begingroup\$ You may be able to replace )%2and sum with )%2*sum, saving three bytes. \$\endgroup\$ – Jonathan Frech Sep 5 '17 at 22:28
  • 1
    \$\begingroup\$ is there a reason for python 3? otherwise u can use ` for str repr \$\endgroup\$ – Maltysen Sep 5 '17 at 22:41
  • 1
    \$\begingroup\$ You can get rid of k entirely and save another seven bytes \$\endgroup\$ – Jonathan Allan Sep 5 '17 at 23:06
  • 8
    \$\begingroup\$ I will confess, I completely lost track of how this works a few minutes ago. >_< \$\endgroup\$ – totallyhuman Sep 5 '17 at 23:12
  • 2
    \$\begingroup\$ Bitwise tricks for -1 byte \$\endgroup\$ – Mr. Xcoder Sep 6 '17 at 4:52
6
\$\begingroup\$

Mathematica, 58 bytes

1-indexed

If[#!=9,#0@If[OddQ@#,Total@IntegerDigits[#^2],#/2+1]+1,0]&

Try it online! (in order to work on Mathics, Tr is replaced with Total)

here is -1 byte version by @JungHwanMin (but it doesn't work on mathics so I kept both)

Mathematica, 57 bytes

If[#!=9,#0@If[2∣#,#/2+1,Total@IntegerDigits[#^2]]+1,0]&
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -1 byte: Use 2∣# instead of OddQ@# and swap the two expressions of If. \$\endgroup\$ – JungHwan Min Sep 6 '17 at 1:44
6
\$\begingroup\$

JavaScript (ES6), 59 50 bytes

0-indexed.

f=n=>n-9&&f(n%2?eval([...""+n*n].join`+`):n/2+1)+1

Try it

o.innerText=(
f=n=>n-9&&f(n%2?eval([...""+n*n].join`+`):n/2+1)+1
)(i.value=5);oninput=_=>o.innerText=f(+i.value)
<input id=i min=3 type=number><pre id=o>


Explanation

The first thing we do is calculate n-9. If n==9 then that, obviously, gives 0 and things stop there. If n!=9 then n-9 will give a non-zero value which, being truthy, means we can continue on through the logical AND. We call the function again, passing a new n to it, calculated as follows:

n%2?

If n modulo 2 is truthy - i.e., n is odd.

[...""+n*n]

Multiply n by itself, convert it to a string and destructure that string to an array of individual characters (digits).

 .join`+`

Rejoin the characters to a string using +, giving us a mathematical expression.

eval(                   )

Evaluate that expression, giving us the sum of the digits of n*n.

:n/2+1

If n%2 is falsey (i.e., n is even) then we simply divide n by 2 and add 1.

To the result of calling the function again, we then add 1. So, using an initial input of 5, the process goes as follows:

f(5)
= -4&&f(7)+1
= -2&&(f(13)+1)+1
=  4&&((f(16)+1)+1)+1
=  7&&(((f(9)+1)+1)+1)+1
=     (((0+1)+1)+1)+1
= 4
\$\endgroup\$
4
\$\begingroup\$

Jelly,  16  15 bytes

-1 byte thanks to miles (use of ternary if)

²DSµH‘µḂ?_9$пL

A monadic link taking and returning numbers.
1-indexed

Try it online! or see a test-suite (coerces results to be 0-indexed and formats like OP code-block)

How?

²DSµH‘µḂ?_9$пL - Link: number, n
            п  - collect results in a list while:
           $    -   last two links as a monad:
         _9     -     subtract nine
        ?       -   if:
       Ḃ        -     bit - current loop input modulo by 2 (1 if odd, 0 if even)
   µ            -   ...then:
²               -     square the current loop input
 D              -     cast to a list of its decimal digits
  S             -     sum
      µ         -   ...else:
    H           -     halve current loop input
     ‘          -     increment
              L - length (get the number of results collected
                -         - this includes the 9, so is 1-indexed w.r.t. k)
\$\endgroup\$
1
  • \$\begingroup\$ I believe you can save a byte combining the if-statement I used with your while loop. ²DSµH‘$Ḃ?n9$пL \$\endgroup\$ – miles Sep 5 '17 at 23:52
4
\$\begingroup\$

Haskell, 62 59 bytes

f 9=0
f a=1+f(cycle[div a 2+1,sum[read[d]|d<-show$a^2]]!!a)

Try it online!

Edit: -3 bytes thanks to @Ørjan Johansen.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ last$x:[y|odd a] can be shortened to cycle[x,y]!!a. \$\endgroup\$ – Ørjan Johansen Sep 6 '17 at 6:27
2
\$\begingroup\$

Perl 5, 56 + 1 (-n) = 57 bytes

$|++,$_=$_%2?eval$_**2=~s/./+$&/gr:1+$_/2while$_-9;say$|

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ This gives no output for 9. \$\endgroup\$ – Shaggy Sep 5 '17 at 23:26
  • \$\begingroup\$ Nothing is the same as 0, right? :) Code changed. \$\endgroup\$ – Xcali Sep 6 '17 at 1:39
2
\$\begingroup\$

05AB1E, 16 bytes

[Ð9Q#Èi2÷>ënSO]N

Try it online!

Explanation

[                  # start a loop
 Ð                 # triplicate current number
  9Q#              # if it equals 9, break
     Èi            # if even
       2÷>         # divide by 2 and increment
          ë        # else
           n       # square
            SO     # sum digits
              ]    # end loop
               N   # push the iteration counter N
\$\endgroup\$
1
\$\begingroup\$

VB.NET (.NET 4.5.2), 107 + 20 (imports) = 117 bytes

Requires Imports System.Linq

Function A(n)
While n<>9
n=If(n Mod 2=0,n/2+1,CStr(n^2).Sum(Function(c)Val(c)))
A+=1
End While
End Function

Function which takes n as an integer input and returns a 0-based k.

Ungolfed:

Function A(n) ' input/output types are Object, but we will be casting to integer
    'A = 0 ' VB will create an implicit variable with the same name as the function

    ' loop until a(n, k) = 9
    ' using n as the variable to store a(n, k)
    While n <> 9

        n = If(n Mod 2 = 0, ' equivalent to c# ternary ?: operator

            n / 2 + 1, ' even case

            CStr(n ^ 2).Sum(Function(c) Val(c)))
            ' odd case
            ' cast number to string
            ' then convert each char to the number it represents
            ' and do a linq sum

        A += 1 ' Object + Integer will coerce to an integer
    End While

    ' Where's the return?
    ' That implicit variable with the matching name will get returned if there's no explicit return
End Function
\$\endgroup\$
1
\$\begingroup\$

Golfscript, 34 bytes

Try it online!

I really need a better way than I have to add up the digits of a number.

~{9-}{.2%{.*`{+48-}*48-}{2/)}if}/,
\$\endgroup\$
1
\$\begingroup\$

Pyth,  23  22 bytes

For now, this is a recursive function but I'll try to switch to .W (functional while) to save bytes instead.

L&-b9hy|*%b2sj^b2Th/b2

Try it here! (with additional code to call the function - use y<your_number> - without spaces)

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

Java 8, 110 98 bytes

n->{int k=0,s;for(;n!=9;k++){s=0;for(int c:(n*n+"").getBytes())s+=c-48;n=n%2<1?n/2+1:s;}return k;}

0-indexed

Explanation:

Try it here.

 n->             // Method with integer as both input and return-type
   int k=0,      //  Result-integer `k` starting at 0
       s;        //  Sum-integer
   for(;n!=9;    //  Loop (1) as long as `n` is not 9
        k++){    //    And increase `k` by 1 after every iteration
     s=0;        //   Reset sum `s` to 0
     for(int c:(n*n+"").getBytes())
                 //   Do `n*n` and inner loop (2) over the digits as characters
       s+=c-48;  //    And increase the sum `s` with these digits
                 //   End of inner loop (2) (implicit / single-line body)
     n=n%2<1?    //   If `n` is even:
        n/2+1    //    Change `n` to `n/2+1`
       :         //   Else:
        s;       //    Change `n` to sum `s`
  }              //  End of loop (1)
  return k;      //  Return the result `k`
}                // End of separated method (2)
\$\endgroup\$
1
\$\begingroup\$

Clojure v1.8, 124 113 112 bytes

0-indexed

(fn[n](loop[a n k 0](if(= a 9)k(recur(if(even? a)(+(/ a 2)1)(apply +(map #(-(int %)48)(str(* a a)))))(inc k)))))

Try it online!

Explanation

(loop[a n k 0](if(= a 9)...))  Loop until a=9
(if(even? a)(+(/ a 2)1)...)    If even, a(n, k) / 2 + 1 if a(n, k)
(if(even? a)...(apply +(map #(-(int %)48)(str(* a a)))))  If odd, calculate the sum of digits of a(n, k)²
#(-(int %)48)                  Convert character to number
\$\endgroup\$
1
\$\begingroup\$

Pyth, 18 bytes

tl.u?%N2sj*NNTh/N2

Try it online: Demonstration

Explanation:

tl.u?%N2sj*NNTh/N2
  .u                 apply the following function to the input, 
                     until it runs into a fixed point
    ?%N2                if value % 2 == 1:
          *NN               value * value
         j   T              convert to digits
        s                   sum
                        else:
               /N2          value / 2
              h              + 1
 l                   get the length of all visited values
t                     - 1
\$\endgroup\$
1
\$\begingroup\$

Japt, 22 21 bytes

0-indexed.

NcUÆ=v ?U/2Ä:U²ìxà b9

Try it


Explanation

Implicit input of integer U.

UÆ             Ã

Generate an array of integers from 0 to U-1 and pass each through a function.

=

Set the value of U.

v ?

If U is divisible by 2.

U/2Ä

U divided by 2, plus 1 (Ä).

:U²ìx

Else: U to the power of 2 (²), split to an array of digits (ì) and reduced by addition (x).

Nc

Append the resulting array to the array of inputs.

b9

Find the index of the first occurrence of 9 in the array. Implicitly output the result.

\$\endgroup\$
3
  • \$\begingroup\$ Dang. I had a feeling using a function method would be a lot better, but I only got it down to 23 bytes: @¥9}a@=u ?U²ìx :U/2Ä;°T If only there were a method that returned the number of iterations until a value stopped changing... \$\endgroup\$ – ETHproductions Sep 6 '17 at 17:27
  • \$\begingroup\$ @ETHproductions: That outputs 1 for 9 instead of 0, but here's a 22 byte version (which still fails for 9). \$\endgroup\$ – Shaggy Sep 6 '17 at 18:15
  • \$\begingroup\$ I did come up with a 20 byte version last night but it had the same issue. \$\endgroup\$ – Shaggy Sep 6 '17 at 18:20

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.