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\$ Sep 6, 2017 at 2:03
  • 1
    \$\begingroup\$ Cool sequence. Did you discover this yourself? \$\endgroup\$ Sep 6, 2017 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, 2017 at 9:42
  • \$\begingroup\$ After Collatz conjecture, Arnauld's Conjecture! What's next? \$\endgroup\$
    – sergiol
    Sep 6, 2017 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\$ Sep 6, 2017 at 16:42

17 Answers 17

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, 2017 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, 2017 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\$ Sep 5, 2017 at 22:28
  • 1
    \$\begingroup\$ is there a reason for python 3? otherwise u can use ` for str repr \$\endgroup\$
    – Maltysen
    Sep 5, 2017 at 22:41
  • 1
    \$\begingroup\$ You can get rid of k entirely and save another seven bytes \$\endgroup\$ Sep 5, 2017 at 23:06
  • 8
    \$\begingroup\$ I will confess, I completely lost track of how this works a few minutes ago. >_< \$\endgroup\$ Sep 5, 2017 at 23:12
  • 2
    \$\begingroup\$ Bitwise tricks for -1 byte \$\endgroup\$
    – Mr. Xcoder
    Sep 6, 2017 at 4:52
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, 2017 at 11:21
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\$ Sep 6, 2017 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, 2017 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\$ Sep 6, 2017 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, 2017 at 23:26
  • \$\begingroup\$ Nothing is the same as 0, right? :) Code changed. \$\endgroup\$
    – Xcali
    Sep 6, 2017 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\$ Sep 6, 2017 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, 2017 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, 2017 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.