Hacker News Reader

Comment by imperialdrive | Hacker News Reader

I know so little about programming but this video absolutely left me up late trying to follow along:

    $count = 1
    do {
        $count++
        $i = $count
        [string]$array = "$i"
        $range = $i - 1
            do {
                if ($i % 2 -eq 0) {$i = $i / 2} else {$i = (3 \* $i) + 1} 
                $array = "$array" + ",$i"
                if ($i - $count -gt $range) {$range = $i - $count}
                if ($i -eq 2) {$i = "Break"}
                } while ($i -ne "Break")
            $array = "$array" + ",1"
            $hits = (($array -split ",") | Measure-Object).count
            Set-Content -Path "${count}_${hits}Hits_${range}MaxRange.txt" -Value "$array" -NoNewline -Force
        } while ($count -lt 1000)

Does anyone know how to make this work with big numbers? At a certain point the value gets returned with something like 2.05891132094649E+44 at which point I can no longer simply add 1 to it.

Edit: Found it... $count = [bigint][math]::pow(10,44) Awesome! I love code!

View on HN

I found in Wikipedia that Somebody Else™ checked that there are no counterexamples up until 2^68.

So my attempt to find a counterexample is to start at (2^68)+1, and perform the 3x+1 or halving until I get to a number that's lower than the one I'm testing - then I know it's not a counterexample.

Since even numbers start by halving (ie, getting lower), I only test odd numbers.

295147905503560000001 and counting. No counter-examples found yet.

Here's a C# example:

  using System.Numerics;
  using System;

  var myBigStartingNumber = BigInteger.Parse("12893123812148934789012378957891325789012357891238912319824589123589012358915891589158989125");
  Collatz(myBigStartingNumber);
  Console.WriteLine("Collatz returned 1");
        
  static int Collatz(BigInteger x)
  {
      Console.WriteLine(x);
      return x == 1 ? 1 : x % 2 == 0 ? Collatz(x / 2) : Collatz(3 * x + 1);
  }

(stack overflows virtually guaranteed!)

Yes, unless C# does tail call elimination (it doesn't, right? I'm a bit behind the times on such things) that will blow through the stack very quickly.

But something which is worth doing while playing with such programs, (besides writing it nonrecursively), is looking into alternative BigNum representations. Tree based number representations can make huge numbers expressible through few operations much smaller, at the cost of making "typical" numbers (those that can't be expressed by arithmetic expressions much shorter than themselves) only slightly larger.

Knuth made one such representation, called TCALC, which lets you do arithmetic on numbers far too large to fit into computer memory in regular byte string bignum representation. A US academic, Paul Tarau, has made similar huge-num libraries (slightly more elegant since representations are unique) for modern programming languages.

Reply on news.ycombinator.com