Juggler sequence: Difference between revisions

Content added Content deleted

Inline

Revision as of 18:03, 18 August 2021

Description

A juggler sequence is an integer sequence that starts with a positive integer a[0], with each subsequent term in the sequence being defined by the recurrence relation:

a[k + 1] = floor(a[k] ^ 0.5) if k is even or a[k + 1] = floor(a[k] ^ 1.5) if k is odd.

If a juggler sequence reaches 1, then all subsequent terms are equal to 1. This is known to be the case for initial terms up to 1,000,000 but it is not known whether all juggler sequences after that will eventually reach 1.

Task

Compute and show here the following statistics for juggler sequences with an initial term of a[n] where n is between 20 and 39 inclusive:

l[n] - the number of terms needed to reach 1.
h[n] - the maximum value reached in that sequence.
i[n] - the index of the term (starting from 0) at which the maximum is (first) reached.

If your language supports big integers with an integer square root function, also compute and show here the same statistics for as many as you reasonably can of the following values for n:

113, 173, 193, 2183, 11229, 15065, 15845, 30817, 48443, 275485, 1267909, 2264915, 5812827

Those with fast languages and fast machines may also like to try their luck at n = 7110201.

However, as h[n] for most of these numbers is thousands or millions of digits long, show instead of h[n]:

d[n] - the number of digits in h[n]

The results can be (partially) verified against the table here.

Related task

Hailstone sequence

See also

oeis:A007320 Number of steps needed for Juggler sequence started at n to reach 1
oeis:A094716 Largest value in the Juggler sequence started at n

Go

Translation of: Wren

Library: Go-rcu

Library: GMP(Go wrapper)

This originally took about 13.5 minutes to reach n = 5,812,827 on my machine (Intel core i7-8565U) using Go's native 'math/big' package.

However, when I exchanged that for Go's GMP wrapper there was a massive speed-up (now only 6.4 seconds to reach n = 5,812,827) and even 7,110,201 became viable with an overall time of 1 minute 40 seconds. <lang go>package main

import (

   "fmt"
   "log"
   // "math/big"
   big "github.com/ncw/gmp"
   "rcu"

)

var zero = new(big.Int) var one = big.NewInt(1) var two = big.NewInt(2)

func juggler(n int64) (int, int, *big.Int, int) {

   if n < 1 {
       log.Fatal("Starting value must be a positive integer.")
   }
   count := 0
   maxCount := 0
   a := big.NewInt(n)
   max := big.NewInt(n)
   tmp := new(big.Int)
   for a.Cmp(one) != 0 {
       if tmp.Rem(a, two).Cmp(zero) == 0 {
           a.Sqrt(a)
       } else {
           tmp.Mul(a, a)
           tmp.Mul(tmp, a)
           a.Sqrt(tmp)
       }
       count++
       if a.Cmp(max) > 0 {
           max.Set(a)
           maxCount = count
       }
   }
   return count, maxCount, max, len(max.String())

}

func main() {

   fmt.Println("n    l[n]  i[n]  h[n]")
   fmt.Println("-----------------------------------")
   for n := int64(20); n < 40; n++ {
       count, maxCount, max, _ := juggler(n)
       cmax := rcu.Commatize(int(max.Int64()))
       fmt.Printf("%2d    %2d   %2d    %s\n", n, count, maxCount, cmax)
   }
   fmt.Println()
   nums := []int64{
       113, 173, 193, 2183, 11229, 15065, 15845, 30817,
       48443, 275485, 1267909, 2264915, 5812827, 7110201
   }
   fmt.Println("     n      l[n]   i[n]   d[n]")
   fmt.Println("-----------------------------------")
   for _, n := range nums {
       count, maxCount, _, digits := juggler(n)
       cn := rcu.Commatize(int(n))
       fmt.Printf("%9s   %3d    %3d    %s\n", cn, count, maxCount, rcu.Commatize(digits))
   }

}</lang>

Output:

n    l[n]  i[n]  h[n]
-----------------------------------
20     3    0    20
21     9    4    140
22     3    0    22
23     9    1    110
24     3    0    24
25    11    3    52,214
26     6    3    36
27     6    1    140
28     6    3    36
29     9    1    156
30     6    3    36
31     6    1    172
32     6    3    36
33     8    2    2,598
34     6    3    36
35     8    2    2,978
36     3    0    36
37    17    8    24,906,114,455,136
38     3    0    38
39    14    3    233,046

     n      l[n]   i[n]   d[n]
-----------------------------------
      113    16      9    27
      173    32     17    82
      193    73     47    271
    2,183    72     32    5,929
   11,229   101     54    8,201
   15,065    66     25    11,723
   15,845   139     43    23,889
   30,817    93     39    45,391
   48,443   157     60    972,463
  275,485   225    148    1,909,410
1,267,909   151     99    1,952,329
2,264,915   149     89    2,855,584
5,812,827   135     67    7,996,276
7,110,201   205    119    89,981,517

Nim

Using only standard library, so limited to values of n less than 40. <lang Nim>import math, strformat

func juggler(n: Positive): tuple[count: int; max: uint64; maxIdx: int] =

 var a = n.uint64
 result = (0, a, 0)
 while a != 1:
   let f = float(a)
   a = if (a and 1) == 0: sqrt(f).uint64
       else: uint64(f * sqrt(f))
   inc result.count
   if a > result.max:
     result.max = a
     result.maxIdx = result.count

echo "n l[n] h[n] i[n]" echo "——————————————————————————————" for n in 20..39:

 let (l, h, i) = juggler(n)
 echo &"{n}   {l:2}  {h:14}     {i}"</lang>

Output:

n   l[n]            h[n]  i[n]
——————————————————————————————
20    3              20     0
21    9             140     4
22    3              22     0
23    9             110     1
24    3              24     0
25   11           52214     3
26    6              36     3
27    6             140     1
28    6              36     3
29    9             156     1
30    6              36     3
31    6             172     1
32    6              36     3
33    8            2598     2
34    6              36     3
35    8            2978     2
36    3              36     0
37   17  24906114455136     8
38    3              38     0
39   14          233046     3

Perl

<lang perl>#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Juggler_sequence use warnings; use Math::BigInt lib => 'GMP';

print " n l(n) i(n) h(n) or d(n)\n"; print " ------- ---- ---- ------------\n"; for my $i ( 20 .. 39,

 113, 173, 193, 2183, 11229, 15065, 15845, 30817,
 48443, 275485, 1267909, 2264915, 5812827,
 7110201  # tried my luck, luck takes about 94 seconds
 )
 {
 my $max = my $n = Math::BigInt->new($i);
 my $at = my $count = 0;
 while( $n > 1 )
   {
   $n = sqrt( $n & 1 ? $n ** 3 : $n );
   $count++;
   $n > $max and ($max, $at) = ($n, $count);
   }

 if( length $max < 27 )
   {
   printf "%8d  %4d  %3d  %d\n", $i, $count, $at, $max;
   }
 else
   {
   printf "%8d  %4d  %3d  d(n) = %d digits\n", $i, $count, $at, length $max;
   }
 }</lang>

Output:

       n  l(n) i(n)  h(n) or d(n)
 -------  ---- ----  ------------
      20     3    0  20
      21     9    4  140
      22     3    0  22
      23     9    1  110
      24     3    0  24
      25    11    3  52214
      26     6    3  36
      27     6    1  140
      28     6    3  36
      29     9    1  156
      30     6    3  36
      31     6    1  172
      32     6    3  36
      33     8    2  2598
      34     6    3  36
      35     8    2  2978
      36     3    0  36
      37    17    8  24906114455136
      38     3    0  38
      39    14    3  233046
     113    16    9  d(n) = 27 digits
     173    32   17  d(n) = 82 digits
     193    73   47  d(n) = 271 digits
    2183    72   32  d(n) = 5929 digits
   11229   101   54  d(n) = 8201 digits
   15065    66   25  d(n) = 11723 digits
   15845   139   43  d(n) = 23889 digits
   30817    93   39  d(n) = 45391 digits
   48443   157   60  d(n) = 972463 digits
  275485   225  148  d(n) = 1909410 digits
 1267909   151   99  d(n) = 1952329 digits
 2264915   149   89  d(n) = 2855584 digits
 5812827   135   67  d(n) = 7996276 digits
 7110201   205  119  d(n) = 89981517 digits

Raku

Reaches 30817 fairly quickly but later values suck up enough memory that it starts thrashing the disk cache and performance drops off a cliff (on my system). Killed it after 10 minutes and capped list at 30817. Could rewrite to not try to hold entire sequence in memory at once, but probably not worth it. If you want sheer numeric calculation performance, Raku is probably not where it's at.

<lang perl6>use Lingua::EN::Numbers; sub juggler (Int $n where * > 0) { $n, { $_ +& 1 ?? .³.&isqrt !! .&isqrt } … 1 }

sub isqrt ( \x ) { my ( $X, $q, $r, $t ) = x, 1, 0 ;

   $q +<= 2 while $q ≤ $X ;
   while $q > 1 {
       $q +>= 2; $t = $X - $r - $q; $r +>= 1;
       if $t ≥ 0 { $X = $t; $r += $q }
   }
   $r

}

say " n l[n] i[n] h[n]"; for 20..39 {

   my @j = .&juggler;
   my $max = @j.max;
   printf "%2s %4d  %4d    %s\n", .&comma, +@j-1, @j.first(* == $max, :k), comma $max;

}

say "\n n l[n] i[n] d[n]"; ( 113, 173, 193, 2183, 11229, 15065, 15845, 30817 ).hyper(:1batch).map: {

   my $start = now;
   my @j = .&juggler;
   my $max = @j.max;
   printf "%10s %4d   %4d %10s   %6.2f seconds\n", .&comma, +@j-1, @j.first(* == $max, :k),
     $max.chars.&comma, (now - $start);

}</lang>

Output:

 n  l[n]  i[n]   h[n]
20    3     0    20
21    9     4    140
22    3     0    22
23    9     1    110
24    3     0    24
25   11     3    52,214
26    6     3    36
27    6     1    140
28    6     3    36
29    9     1    156
30    6     3    36
31    6     1    172
32    6     3    36
33    8     2    2,598
34    6     3    36
35    8     2    2,978
36    3     0    36
37   17     8    24,906,114,455,136
38    3     0    38
39   14     3    233,046

      n     l[n]   i[n]    d[n]
       113   16      9         27     0.01 seconds
       173   32     17         82     0.01 seconds
       193   73     47        271     0.09 seconds
     2,183   72     32      5,929     1.05 seconds
    11,229  101     54      8,201     1.98 seconds
    15,065   66     25     11,723     2.05 seconds
    15,845  139     43     23,889    10.75 seconds
    30,817   93     39     45,391    19.60 seconds

Wren

Library: Wren-fmt

Library: Wren-big

This took about 14.5 minutes to reach n = 15,845 on my machine and I gave up after that. <lang ecmascript>import "/fmt" for Fmt import "/big" for BigInt

var zero = BigInt.zero var one = BigInt.one var two = BigInt.two

var juggler = Fn.new { |n|

   if (n < 1) Fiber.abort("Starting value must be a positive integer.")
   var a = BigInt.new(n)
   var count = 0
   var maxCount = 0
   var max = a.copy()
   while (a != one) {
       if (a.isEven) {
           a = a.isqrt
       } else {
           a = (a.square * a).isqrt
       }
       count = count + 1
       if (a > max) {
           max = a
           maxCount = count
       }
   }
   return [count, maxCount, max, max.toString.count]

}

System.print("n l[n] i[n] h[n]") System.print("-----------------------------------") for (n in 20..39) {

   var res = juggler.call(n)
   Fmt.print("$2d    $2d   $2d    $,i", n, res[0], res[1], res[2])

} System.print() var nums = [113, 173, 193, 2183, 11229, 15065, 15845] System.print(" n l[n] i[n] d[n]") System.print("----------------------------") for (n in nums) {

   var res = juggler.call(n)
   Fmt.print("$,6d   $3d    $3d   $,6i", n, res[0], res[1], res[3])

}</lang>

Output:

n    l[n]  i[n]  h[n]
-----------------------------------
20     3    0    20
21     9    4    140
22     3    0    22
23     9    1    110
24     3    0    24
25    11    3    52,214
26     6    3    36
27     6    1    140
28     6    3    36
29     9    1    156
30     6    3    36
31     6    1    172
32     6    3    36
33     8    2    2,598
34     6    3    36
35     8    2    2,978
36     3    0    36
37    17    8    24,906,114,455,136
38     3    0    38
39    14    3    233,046

n        l[n]   i[n]   d[n]
----------------------------
   113    16      9       27
   173    32     17       82
   193    73     47      271
 2,183    72     32    5,929
11,229   101     54    8,201
15,065    66     25   11,723
15,845   139     43   23,889