lambdaway :: hamming

1 | list | login |load

| |

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

_h2 1) compute

_p Build a table of {b 2{sup i}•3{sup j}•5{sup k}} from {b i,j,k = 0} to {b n} and sort it.

{prewrap
'{def ham
 {lambda {:n}
  {S.sort <
   {S.map {{lambda {:n :i}
   {S.map {{lambda {:n :i :j} ;; {div}
   {S.map {{lambda {:i :j :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} }
}}} 
-> {def ham
 {lambda {:n}
  {S.sort <
   {S.map {{lambda {:n :i}
   {S.map {{lambda {:n :i :j} ;; {div}
   {S.map {{lambda {:i :j :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} }
}}}

'{def H {ham 30}}
-> {def H {ham 30}}

'{S.slice 0 19 {H}}
-> {S.replace , by space in {S.slice 0 19 {H}}}

'{S.get 1690 {H}} 
-> {S.get 1690 {H}}  
  
}

_h2 2) display
_p Display a hamming number as 2{sup a}•3{sup b}•5{sup c}

{pre
'{def factor
 {def factor.r
  {lambda {:n :i}
   {if {> :i :n}
    then 
    else {if {= {% :n :i} 0}
    then :i {factor.r {/ :n :i} :i}
    else {factor.r :n {+ :i 1}} }}}}
 {lambda {:n}
  :n is the product of 1 {factor.r :n 2} }}
-> {def factor
 {def factor.r
  {lambda {:n :i}
   {if {> :i :n}
    then 
    else {if {= {% :n :i} 0}
    then :i {factor.r {/ :n :i} :i}
    else {factor.r :n {+ :i 1}} }}}}
 {lambda {:n}
  :n is the product of 1 {factor.r :n 2} }}

'{def asproductofpowers
 {def asproductofpowers.loop
  {lambda {:a :b :c :n}
   {if {= {S.first :n} 1}
    then 2{sup :a}•3{sup :b}•5{sup :c}
    else {asproductofpowers.loop
          {if {= {S.first :n} 2} then {+ :a 1} else :a}
          {if {= {S.first :n} 3} then {+ :b 1} else :b}
          {if {= {S.first :n} 5} then {+ :c 1} else :c}
          {W.rest :n} }
 }}}
 {lambda {:n}
  {asproductofpowers.loop 0 0 0 {S.reverse :n}}}}
-> {def asproductofpowers
 {def asproductofpowers.loop
  {lambda {:a :b :c :n}
   {if {= {S.first :n} 1}
    then 2{sup :a}•3{sup :b}•5{sup :c}
    else {asproductofpowers.loop
          {if {= {S.first :n} 2} then {+ :a 1} else :a}
          {if {= {S.first :n} 3} then {+ :b 1} else :b}
          {if {= {S.first :n} 5} then {+ :c 1} else :c}
          {W.rest :n} }
 }}}
 {lambda {:n}
  {asproductofpowers.loop 0 0 0 {S.reverse :n}}}}

'{factor 2125764000}
-> {factor 2125764000}

'{asproductofpowers {factor 2125764000}}
-> {asproductofpowers {factor 2125764000}}

'{S.map {lambda {:i} {div}:i: {S.get :i {H}} =
                    {asproductofpowers {factor {S.get :i {H}}}}} 
       {S.serie 0 19}}
->
{S.map {lambda {:i} {div}:i: {S.get :i {H}} = {asproductofpowers {factor {S.get :i {H}}}}} {S.serie 0 19}}

}

{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['BI.min'] = function() {   // {BI.min a b c}
  var args = arguments[0].trim().split(" "),
         a = BigInt(args[0]),
         b = BigInt(args[1]),
         c = BigInt(args[2]); 
  return ((a < b) && (a < c)) ?
          a : ((b < a) && (b < c)) ?
          b : c
};
*/

LAMBDATALK.DICT['BI.min'] = function() {   // {BI.min a b}
  var args = arguments[0].trim().split(" "),
         a = BigInt(args[0]),
         b = BigInt(args[1]);
  return ( a < b ) ? a : b
};

LAMBDATALK.DICT['removedup'] = function() {  // {removedup a b c ...}
  var args = arguments[0].trim().split(" ");
  var out = [args[0]];
  for (var i=1; i < args.length; i++)
    if (args[i] !== args[i-1]) out.push( args[i] )
  return out.join(" ")
};

}