lambdaway :: hamming

2 | list | login |load

| |

_h1 hamming number | 1 | [[2|?view=hamming_numbers2]] | [[3|?view=hamming_numbers3]] | [[4|?view=hamming_numbers4]]

_p Following [[https://rosettacode.org/wiki/Hamming_numbers|https://rosettacode.org/wiki/Hamming_numbers]]: 
_h2 {code H = 2{sup i} × 3{sup j} × 5{sup k} where i,  j,  k  ≥  0}

{prewrap

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400 405
 
H(1691) -> 2125764000

'{S.reduce BI.* {BI.** 2 6}
               {BI.** 3 0}
               {BI.** 5 0}}
-> {S.reduce BI.* {BI.** 2 6}
               {BI.** 3 0}
               {BI.** 5 0}}

{def removedup
 {def removedup.loop
  {lambda {:a :b}
   {if {A.empty? :a}
    then :b
    else {removedup.loop {A.rest :a} 
                         {if {= {A.in? {A.first :a} :b} -1}
                          then {A.addlast! {A.first :a} :b} 
                          else :b}}}}}
 {lambda {:s}
  {S.replace (\[|\]|,) by space in
   {A.disp
    {removedup.loop {A.new :s} {A.new}}}}}}

'{def ham
 {lambda {:n}
  {S.sort <
   {S.map {{lambda {:n :i}
   {S.map {{lambda {:n :i :j} 
   {S.map {{lambda {:i :j :k}
                   {S.reduce BI.* {BI.** 2 :i}
                                  {BI.** 3 :j} 
                                  {BI.** 5 :k}}} :i :j} 
   {S.serie 0 :n} } } :n :i}
   {S.serie 0 :n} } } :n}
   {S.serie 0 :n} }
}}}
-> {def ham
 {lambda {:n}
  {S.sort < 
   {S.map {{lambda {:n :i}
   {S.map {{lambda {:n :i :j} 
   {S.map {{lambda {:i :j :k} 
                 ;;  2{sup :i}x3{sup :j}x5{sup :k}
                 ;;  {BI.* {BI.** 2 :i} {BI.* {BI.** 3 :j} {BI.** 5 :k}}}
                   {* {pow 2 :i} {pow 3 :j} {pow 5 :k}}
           } :i :j} 
   {S.serie 0 :n} } } :n :i}
   {S.serie 0 :n} } } :n} 
   {S.serie 0 :n} }   
 }
}}

'{S.last {ham 3}}

'{S.slice 0 19 {ham 5}}
-> '{S.slice 0 19 {ham 5}}

'{S.get 1690 {ham 30}}   // 31,32,... idem
-> 2125764000

'{S.get 1999 {ham 32}}
-> 8062156800

'{S.get 10000 {ham 58}}  // 59,60,... idem
-> 288555831593533440

No 1690 | 2125764000 = 2^5*3^12*5^3 
                     = '{* {pow 2 5} {pow 3 12} {pow 5 3}}

{hr}

From [[BASIC256|https://rosettacode.org/wiki/Hamming_numbers#BASIC256]]

function hamming( limit)
    h( 0) =1
    x2 =2: x3 =3: x5 =5
    i  =0: j  =0: k  =0
    for n =1 to limit
        h( n) = min( x2, min( x3, x5))
        if x2 = h( n) then i = i +1: x2 =2 *h( i)
        if x3 = h( n) then j = j +1: x3 =3 *h( j)
        if x5 = h( n) then k = k +1: x5 =5 *h( k)
    next n
    hamming =h( limit -1)
end function

{def x2 {A.new 2}} = {x2}
{def x3 {A.new 3}} = {x3}
{def x5 {A.new 5}} = {x5}
{def i {A.new 0}}  = {i}
{def j {A.new 0}}  = {j}
{def k {A.new 0}}  = {k}

{def h {A.new 1}} = {A.last {h}}

{def a++
 {lambda {:a}
  {A.set! 0 {+ {A.get 0 :a} 1} :a}}}

{def iham
 {lambda {:n}
   {S.map {lambda {:n}
            {let { {:n :n}
                   {:h {A.set! :n {min {A.get 0 {x2}}
                                       {A.get 0 {x3}}
                                       {A.get 0 {x5}}} {h}}}
                 }

{if {= {A.get 0 {x2}} {A.get :n :h}}
 then  {A.set! 0 {* 2 {A.get 0 {a++ {i}} :h}} {x2}} else}
{if {= {A.get 0 {x3}} {A.get :n :h}}
 then  {A.set! 0 {* 3 {A.get 0 {a++ {j}} :h}} {x3}} else}
{if {= {A.get 0 {x5}} {A.get :n :h}}
 then  {A.set! 0 {* 5 {A.get 0 {a++ {k}} :h}} {x5}} else}

}
           }       
           {S.serie 1 :n}   
}}}

{S.length {iham 40}}

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400 405

{hr}

'{def H {ham {pow 3 3}}}  -> '{def H {ham {pow 3 3}}}

'{S.length {H}}    -> '{S.length {H}}
'{S.last {H}}      -> '{S.last {H}}

'{A.in? 2125764000 {A.new {H}}} -> '{A.in? 2125764000 {A.new {H}}}

}

_h2 psyco

{pre
From [[psycho|https://rosettacode.org/wiki/Hamming_numbers#Python]]

def hamming(limit):
    h = [1] * limit
    x2, x3, x5 = 2, 3, 5
    i = j = k = 0

for n in xrange(1, limit):
        h[n] = min(x2, x3, x5)
        if x2 == h[n]:
            i += 1
            x2 = 2 * h[i]
        if x3 == h[n]:
            j += 1
            x3 = 3 * h[j]
        if x5 == h[n]:
            k += 1
            x5 = 5 * h[k]

return h[-1]

psyco.bind(hamming)
print [hamming(i) for i in xrange(1, 21)]
print hamming(1691)
print hamming(1000000)
}

_h2 lambdatalk

{prewrap
'{def hamming

{def hamming.test
  {lambda {:h :n :x :a :i}
   {if {= :x {A.get :n :h}}
    then {* :a {A.get {+ :i 1} :h}} {+ :i 1}
    else :x :i} 
 }}

{def hamming.rec
  {lambda {:h :x2 :i :x3 :j :x5 :k :limit :n}
   {hamming.loop :h
                 {hamming.test :h :n :x2 2 :i}
                 {hamming.test :h :n :x3 3 :j}
                 {hamming.test :h :n :x5 5 :k}
                 :limit
                 {+ :n 1} }
 }}

{def hamming.loop
  {lambda {:h :x2 :i :x3 :j :x5 :k :limit :n}
   {if {>= :n :limit}
    then {A.last :h}
    else {hamming.rec {A.set! :n {min :x2 :x3 :x5} :h}
                      :x2 :i :x3 :j :x5 :k :limit :n}
 }}}

{lambda {:n}
  {hamming.loop {A.new 1} 2 0 3 0 5 0 :n 1}
}} 
-> {def hamming
 {def hamming.test
  {lambda {:h :n :x :a :i}
   {if {= :x {A.get :n :h}}
    then {BI.* :a {A.get {+ :i 1} :h}} {+ :i 1}
    else :x :i} 
 }}

{lambda {:limit}
  {hamming.loop {A.new 1} 2 0 3 0 5 0 :limit 1}
}}

'{S.map hamming {S.serie 1 20}} 
-> 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36

'{hamming 1691} 
-> (2125764000)   // stackoverflow

'{min 2 3}
-> {min 2 3}
'{min 1234567890123456789 1234567890123456788}
-> {min 1234567890123456789 1234567890123456788} ???

}

{hr}

{script 
LAMBDATALK.DICT['BigInt'] = function() {
  var args = arguments[0].trim();
  return BigInt( Number(args) )
};

LAMBDATALK.DICT['BI.+'] = function() {
  var args = arguments[0].trim().split(' ');
  return BigInt( args[0] ) + BigInt( args[1] )
};
LAMBDATALK.DICT['BI.-'] = function() {
  var args = arguments[0].trim().split(' ');
  return BigInt( args[0] ) - BigInt( args[1] )
};
LAMBDATALK.DICT['BI.*'] = function() {
  var args = arguments[0].trim().split(' ');
  return BigInt( args[0] ) * BigInt( args[1] )
};
LAMBDATALK.DICT['BI./'] = function() {
  var args = arguments[0].trim().split(' ');
  return BigInt( args[0] ) / BigInt( args[1] )
};
LAMBDATALK.DICT['BI.%'] = function() {
  var args = arguments[0].trim().split(' ');
  return BigInt( args[0] ) % BigInt( args[1] )
};
LAMBDATALK.DICT['BI.**'] = function() {
  var args = arguments[0].trim().split(' ');
  return BigInt( args[0] ) ** BigInt( args[1] )
};

LAMBDATALK.DICT['isPrime'] = function() {

var isPrime = function(p) {
    if ( p === 2n || p === 3n || p === 5n || p === 7n )
      return true
    if ( p < 2 || p % 2n === 0n ) 
      return false
    else 
    for (let i = 3n; i * i <= p; i = i + 2n) {
      if (p % i === 0n) return false;
    }
    return true;
  };

var args = arguments[0].trim();
  return (isPrime(BigInt(args)))? "true" : "false"
};

}