The Recaman's sequence

GS The Recaman's sequence is a sequence invented by Bernardo Recaman Santos (a Colombian mathematician). It is defined by :

 a(0) = 0            
 a(n) = a(n-1) - n     for n > 0, if positive and not already in the sequence
 a(n) = a(n-1) + n     otherwise

The first terms of the sequence are:

 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42, 17, 43, 16, 44, 15, 45, 14, 46, 79, ....

An interesting visualization of this sequence can be done with half-circle representing the jump from a(n) to a(n+1).

img_recaman1

The idea of plotting the Recaman sequence like this come from the YouTube channel Numberphile in a video featuring Alex Bellos and Edmund Harriss.

With n = 100 :

img_recaman2

With n = 200 :

img_recaman3

 # recaman.tcl
 # Author:      Gerard Sookahet
 # Date:        15 Apr 2021
 # Description: Plot Recaman sequence with half-circles
 # Reference : Numberphile - https://www.youtube.com/watch?v=FGC5TdIiT9U

 package require Tk
 bind all <Escape> {exit}

 proc recaman {n} {
  if {$n <= 0} return
  set s {}
  lappend s 0
  set prev 0
  for {set i 1} {$i <= $n} {incr i} {
     set curr [expr {$prev - $i}]
     if {$curr < 0 || $curr in $s} then {set curr [expr {$prev + $i}]}
     lappend s $curr
     set prev $curr
  }
  return $s
 }

 proc plot_recaman {s} {
  set n [llength $s]
  incr n -1
  set z 4
  set H [expr {4*$n}]
  if {$n > 100} then {
    set z 2
    set H [expr {2*$n}]
  }
  set W [expr {9*$n}]
  set n2 [expr {$H/2}]
  pack [canvas .c -background black -width $W -height $H]
  pack [button .b -text Quit -command exit]
 
  set x1 0
  for {set i 1} {$i <= $n} {incr i} {
     set x2 [expr {$z*[lindex $s $i]}]
     set xo [expr {($x2 - $x1)/2}]
     if {$i % 2 == 0} then {
       set y1 [expr {$n2 - $xo}]
       set y2 [expr {$n2 + $xo}]
       set ext 180
     } else {
       set y1 [expr {$n2 + $xo}]
       set y2 [expr {$n2 - $xo}]
       set ext -180
     }
     .c create arc $x1 $y1 $x2 $y2 -extent $ext -style arc -outline blue
     set x1 $x2
  }
 }

 plot_recaman [recaman 100]

Reference :

- Numberphile - https://www.youtube.com/watch?v=FGC5TdIiT9U


For those who estimate codegolfing [L1 ] :

 proc R n {lappend L [expr {$n?[set x [lindex [set L [A [expr $n-1]]] e]]>$n&$x-$n ni$L?$x-$n:$x+$n:0}]}

much faster (ten times!!) Recaman Sequence implementation. the code can also be easily converted for the coroutines/generator

proc recaman { total } {
    if { $total <= 0 } {
        return {}
    }
    set recaman {}
    array set unused {} ; # unused numbers
    set maxnum 1        ; # max of unused +1
    set current 0
    for { set i 1 } { $i<$total } { incr i } {
        set n [ expr { $current - $i } ]
        if { $n > 0 && [ info exists unused($n) ] } {
            unset unused($n)
        } else {
            set n [ expr { $current + $i } ]
            if { $n >= $maxnum } {
                for { set maxnum } { $maxnum < $n } { incr maxnum } {
                    set unused($maxnum) $maxnum
                }
                incr maxnum
            } else {
                if { [ info exists unused($n) ] } {
                    unset unused($n)
                } else {
                    # puts "dup $n"
                }
            }
        }
        set current $n
        lappend recaman $n
    }
    set recaman
}