How to resolve the algorithm Hofstadter-Conway $10,000 sequence step by step in the Picat programming language

Published on 12 May 2024 09:40 PM
#Picat

How to resolve the algorithm Hofstadter-Conway $10,000 sequence step by step in the Picat programming language

Table of Contents

Problem Statement

The definition of the sequence is colloquially described as: Note that indexing for the description above starts from alternately the left and right ends of the list and starts from an index of one. A less wordy description of the sequence is: The sequence begins: Interesting features of the sequence are that:

The sequence is so named because John Conway offered a prize of $10,000 to the first person who could find the first position,   p   in the sequence where It was later found that Hofstadter had also done prior work on the sequence. The 'prize' was won quite quickly by Dr. Colin L. Mallows who proved the properties of the sequence and allowed him to find the value of   n   (which is much smaller than the 3,173,375,556 quoted in the NYT article).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Hofstadter-Conway $10,000 sequence step by step in the Picat programming language

Source code in the picat programming language

go => 
   foreach(N in 0..19)
      [Val,Ix] = argmax({a(I)/I : I in 2**N..2**(N+1)}),
      printf("Max from 2^%2d..2^%-2d is %0.8f at %d\n",N,N+1,Val,Ix+2**N-1)
   end,
   println(mallows_number=mallows_number()),
   nl.

% The sequence definition
table
a(1) = 1.
a(2) = 1.
a(N) = a(a(N-1))+a(N-a(N-1)).

% argmax: find the (first) index for the max value(s) of L.
argmax(L) = [Max,MaxIxFirst] =>
  Max = max(L),
  MaxIxFirst = {I : I in 1..L.length, L[I] == Max}.first.

% Calculate the Mallows number separately.
mallows_number() = Mallow =>
   Mallow = _,   
   foreach(M in 1..19)
      Min = 2**M,
      Max = Min*2,
      MaxRatio = 0,
      NVal = 0,
      foreach(N in Min..Max)
         Ratio = a(N)/N,
         if Ratio > MaxRatio then
           MaxRatio := Ratio,
           NVal := N
         end,
         if Ratio > 0.55 then
           Mallow := N
         end
      end
  end.

You may also check:How to resolve the algorithm Roman numerals/Decode step by step in the Swift programming language
You may also check:How to resolve the algorithm Catamorphism step by step in the Ring programming language
You may also check:How to resolve the algorithm Taxicab numbers step by step in the D programming language
You may also check:How to resolve the algorithm Combinations step by step in the Go programming language
You may also check:How to resolve the algorithm Legendre prime counting function step by step in the Phix programming language