Théorie algorithmique des nombres

 

En dessous de cette expression extrémement exagérée se cache une page avec des procédures de calcul en théorie des nombres (primalité, PGCD, factorisation, etc ....).

Test de primalité

La procédure basique qui renvoie 1 si n est premier.

 proc estpremier n {
  set max [expr {int(sqrt($n))}]
  set d 2
  while {$d <= $max} {
       if {$n%$d == 0} {return 0}
       incr d
  }
  return 1
 }

 % estpremier 19
 % 1

Dans la catégorie des Monolignes d'après une astuce en Perl [1]

 proc estpremier n {expr {$n>1 && ![regexp {^(oo+?)\1+$} [string repeat o $n]]}}

Avec la TclLib (à partir de la version 1.13).

 package require math::numtheory
 ::math::numtheory::isprime 7

Le test de primalité de Miller-Rabin.

 proc MR {n k} {
  if {$n <= 3} {return 1}
  if {$n % 2 == 0} {return 0}

  set d [expr {$n - 1}]
  set s 0
  while {$d % 2 == 0} {
       set d [expr {$d / 2}]
       incr s
  }

  while {$k > 0} {
       incr k -1
       set a [expr {2 + int(rand()*($n - 4))}]
       set x [expr {($a ** $d) % $n}]
       if {$x == 1 || $x == $n - 1} continue
       for {set r 1} {$r < $s} {incr r} {
          set x [expr {($x ** 2) % $n}]
          if {$x == 1} {return 0}
          if {$x == $n - 1} break
       }
       if {$x != $n - 1} {return 0}
  }
  return 1
 }

Facteurs premiers

Procédure qui renvoie la liste des facteurs premiers d'un entier n.

 proc facteurpremier n {
  set res {}
  for {set i 2} {$i <= $n} {incr i} {
     while {$n%$i == 0} {
          set n [expr {$n/$i}]
          lappend res $i
     }
  }
  return $res
 }

 % facteurpremier 344
 % 2 2 2 43

Suite des nombres premiers

Procédure qui renvoie la liste des nombres premiers compris entre 2 et n.

 proc suitepremier n {
  set res [list 2]
  for {set i 3} {$i <= $n} {incr i 2} {
     set max [expr {int(sqrt($i))}]
     foreach j $res {
            if {$j  > $max} {
              lappend res $i
              break
            }
            if {![expr {$i % $j}]} {break}
     }
  }
  return $res
 }

 % suitepremier 102
 % 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101

Voir aussi Spirale d'Ulam

PGCD

La procédure récursive de calcul du PGCD (Plus Grand Commun Diviseur) de deux entiers (p,q).

 proc pgcd {p q} {
  if {$q == 0} {return $p}
  pgcd $q [expr {$p % $q}]
 }

 % pgcd 36 63
 % 9

PPCM

Plus petit commun multiple de deux nombres.

 proc ppcm {p q} {
  set n [expr {$p*$q}]
  if {!$n} {return 0}
  while 1 {
       set p [expr {$p % $q}]
       if {!$p} {return [expr {$n/$q}]}
       set q [expr {$q % $p}]
       if {!$q} {return [expr {$n/$p}]}
  }
 }

 % ppcm 14 18

Indicatrice d'Euler

L'indicatrice d'Euler Phi(n) désigne le nombre d'entiers compris entre 1 et n, et premiers avec n. En anglais on emploie le terme de totient.

 proc pgcd {p q} {
  if {$q == 0} {return $p}
  pgcd $q [expr {$p % $q}]
 }

 proc phi n {
  for {set i 1} {$i <= $n} {incr i} {
     if {[pgcd $i $n] == 1} {incr j}
  }
  return $j
 }

 % phi 19
 % 18

Nombre parfait

Un nombre parfait est un nombre qui est égal à la somme de ses diviseurs. Par exemple 6 = 1 + 2 + 3.

 proc estparfait n {
  set res 0
  for {set i 1} {$i <= $n} {incr i} {
     if {$n % $i == 0} {incr res $i}
  }
  return [expr {$res == 2*$n}]
 }

 % estparfait 6
 % 1

Nombres heureux

un nombre heureux est un nombre entier qui, lorsqu'on ajoute les carrés de chacun de ses chiffres, puis les carrés des chiffres de ce résultat et ainsi de suite jusqu'à l'obtention d'un nombre à un seul chiffre, donne 1 pour résultat.

Par exemple : 19 est un nombre heureux car :

 1*1 + 9*9 = 82
 8*8 + 2*2 = 68
 6*6 + 8*8 = 100
 1*1 + 0*0 + 0*0 = 1

.

 proc sommecarres l {
  set som 0
  foreach n $l {set som [expr {$som + $n**2}]}
  set som
 }

 proc estheureux n {
  set l {}
  while {$n > 1 && [lsearch -exact $l $n] == -1} {
       lappend l $n
       set n [sommecarres [split $n ""]]
  }
  return [expr {$n == 1}]
 }

 % estheureux 19
 % 1

Nombre de Kaprekar

Un nombre de Kaprekar est un nombre qui, lorsqu'il est élevé au carré, peut être séparé en une partie gauche et une partie droite (non nulle) telles que la somme donne le nombre initial.

Par exemple 55 car 55*55 = 3025 sachant que 30 + 25 = 55

 proc estkaprekar n {
  if {$n == 1} {return 1}
  set s [expr {$n*$n}]
  for {set i 1} {$i < [string length $s]} {incr i} {
     scan $s "%${i}d%d" p q
     if {$q && $n == $p + $q} {return 1}
  }
  return 0
 }

 % estkaprekar 55
 % 1

Triplet pythagoricien

Un triplet pythagoricien est un triplet d'entiers naturels non nuls (a,b,c) qui vérifie la relation de Pythagore : a**2 + b**2 = c**2.

 proc pytriplet N {
  for {set a 1} {$a <= $N} {incr a} {
     for {set b $a} {$b <= $N} {incr b} {
        set c [expr {sqrt($a*$a + $b*$b)}]
        if {$c == round($c)} then {
          if [prime $a $b] {puts "$a $b [expr {round($c)}]"}
        }
     }
  }
 }

 proc prime {a b} {
  for {set i 2} {$i <= $a} {incr i} {
     set ai [expr {double($a)/$i}]
     set bi [expr {double($b)/$i}]
     if {$ai == round($ai) && $bi == round($bi)} {return 0}
  }
  return 1
 }

 % pytriplet 20
 3 4 5
 5 12 13
 8 15 17

Voir aussi Triplet pythagoricien

Inverse modulaire

Inverse modulaire d'un entier a pour la multiplication modulo n.

 proc invmod {a n} {
  set n0 $n
  set x0 0
  set x1 1
  if {$n == 1} {return 1}
  while {$a > 1} {
       set q [expr {$a / $n}]
       set t $n
       set n [expr {$a % $n}]
       set a $t
       set t $x0
       set x0 [expr {$x1 - $q*$x0}]
       set x1 $t
  }
  if {$x1 < 0} {incr x1 $n0}
  return $x1
 }

Nombre de Harshad (ou de Niven)

Un nombre de Harshad est un nombre entier qui est divisible par la somme de ses chiffres.

 proc estHarshad n {
  if {$n < 1} {return 0}
  set s [tcl::mathop::+ {*}[split $n ""]]
  return [expr {$n % $s == 0}]
 }

Nombre de Catalan

 proc catalan n {
  set res {}
  array set t {0 0 1 1}
  for {set i 1} {[set k $i] <= $n} {incr i} {
     for {set j $i} {$j > 1} {} {incr t($j) $t([incr j -1])}
     set t([incr k]) $t($i)
     for {set j $k} {$j > 1} {} {incr t($j) $t([incr j -1])}
     lappend res [expr {$t($k) - $t($i)}]
  }
  return $res
 }

 % puts [catalan 11]
 % 1 2 5 14 42 132 429 1430 4862 16796 58786

Catégorie Mathématiques