Un po' di matematica

Qualche funzione di quelle cose che s'incontrano in matematica, roba semplice, da scuola dell'obbligo. E sì, lo so, è solo un gioco.

Prima di cominciare: ci sono dei vincoli, uso Python e Bash invece di mezzi più pratici (e potenti); per esempio c'è Maxima ma anche le REPL dei linguaggi usuali (e meno usuali, ecco Racket:

$ rkt
Welcome to Racket v6.11.
> (require math/number-theory)
> (factorize 823543)
'((7 7))
> (factorize 9657787)
'((9657787 1))
> (factorize 3628800)
'((2 8) (3 4) (5 2) (7 1))
> ^D
$

o Pyhton

$ py3
>>> import math
>>> math.factorial(10)
3628800
>>>
$

Allora parto. Tutti sanno cos'è il fattoriale di un numero ma per quelli come me che la memoria... ecco la Wiki.

In Python è predefinita, nel modulo math per cui lo script è semplicissimo:

#!/usr/bin/python3

from math import factorial
from sys import argv

n = int(argv[1])
print(factorial(n))
ed ecco:

$ py3 fact.py 20
2432902008176640000
$ py3 fact.py 100
933262154439441526816992388562667004907159682643816214685929
638952175999932299156089414639761565182862536979208272237582
51185210916864000000000000000000000000
$

Con Bash invece bisogna farla, ma è altrettanto semplice:

#!/bin/bash

N=$1

F=1 #fattoriale
for (( N ; N > 1 ; N-- )); do
    F=$(( F * N ))
done

echo $F

funziona per numeri non troppo grandi:

$ bash fact.sh 10
3628800
$ bash fact.sh 20
2432902008176640000
$ bash fact.sh 100
0

OOPS! errore qui. Il numero limite è 20, dove 20! ~= 2.433e+18:

$ bash fact.sh 20
2432902008176640000
$ bash fact.sh 21
-4249290049419214848
$

Una soluzione migliore si avrebbe ricorrendo a bc.

Scomposizione del numero in fattori primi, qui la Wiki è solo un abbozzo in italiano, per saperne di più c'è la versione inglese.

Con Linux c'è factor:

$ factor 823543
823543: 7 7 7 7 7 7 7
$ factor 9657787
9657787: 9657787
$ factor 3628800
3628800: 2 2 2 2 2 2 2 2 3 3 3 3 5 5 7
$

In Python manca (o non l'abbiamo trovata) ma si può fare, anzi basta chiedere a Stack Overflow, versione personalizzata:

#!/usr/bin/python3

from sys import argv
from math import sqrt

def factorize(n):
   if n == 0: return [[0, 1]]
   elif n == 1: return [[1, 1]]
   else:
      factors = []
      divisor = 2
      lim = int(sqrt(n))
      while divisor <= lim:
         power = 0
         while (n % divisor) == 0:
            n //= divisor
            power += 1
         if power > 0:
            factors.append([divisor, power])
         divisor += 1
      if len(factors) == 0:
        factors = [n, 1]

      return factors

n = int(argv[1])
print(factorize(n))

ed ecco:

$ py3 comp.py 823543
[[7, 7]]
$ py3 comp.py 9657787
[9657787, 1]
$ py3 comp.py 3628800
[[2, 8], [3, 4], [5, 2], [7, 1]]
$

La versione Bash si potrebbe fare ma per adesso ci accontentiamo di quella predefinita, funziona con numeri grandi, sarebbero solo da raccogliere:

$ rkt
Welcome to Racket v6.11.
> (require math/number-theory)
> (define n (expt 2 64))
> n
18446744073709551616
> (factorize n)
'((2 64))
> ^D
$ factor 18446744073709551616
18446744073709551616: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
$

e anche

$ rkt
Welcome to Racket v6.11.
> (require math/number-theory)
> (define n (* 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))
> n
2305567963945518424753102147331756070
> (factorize n)
'((2 1) (3 1) (5 1) (7 1) (11 1) (13 1) (17 1) (19 1) (23 1)
  (29 1) (31 1) (37 1) (41 1) (43 1) (47 1) (53 1) (59 1)
  (61 1) (67 1) (71 1) (73 1) (79 1) (83 1) (89 1) (97 1))
> ^D
$ factor 2305567963945518424753102147331756070
2305567963945518424753102147331756070: 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 
$

Il massimo comun divisore MCD, conosciuto anche come gcd, è predefinito in Python:

#!/usr/bin/python3

from math import gcd
from sys import argv

if len(argv) != 3:
    print('errore, mancano i due numeri')
    exit(2)

try:
    print(gcd(int(argv[1]), int(argv[2])))
except:
    print('errore di input')
    exit(1)

$ py3 gcd.py 80 15
5 
$ py3 gcd.py 120 18
6
$ py3 gcd.py 120 24
24
$ py3 gcd.py 226553150 1023473145
5
$

La versione Bash

#!/bin/bash

a=$1
b=$2
while [ $b -ne 0 ]; do
  remainder=$(( $a % $b ))
  a=$b
  b=$remainder
done

echo $a

$ bash gcd.sh 80 15
5 
$ bash gcd.sh 120 18
6
$ bash gcd.sh 120 24
24
$ bash gcd.sh 226553150 1023473145
5
$

Infine il minimo comune multiplo, la Wiki qui e qui.

La versione Python è immediata:

#!/usr/bin/python3

from sys import argv
from math import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

a = int(argv[1])
b = int(argv[2])

print(lcm(a, b))

$ py3 lcm.py 80 15
240
$ py3 lcm.py 21 6
42
$ py3 lcm.py 7 823543
823543

Per Bash si può usare gcd.sh:

#!/bin/bash

GCD=$(. ./gcd.sh $1 $2)
echo $(( $1 * $2 / $GCD ))

$ bash lcm.sh 80 15
240
$ bash lcm.sh 21 6
42
$ bash lcm.sh 7 823543
823543
$

OK, per adesso basta così, Il post è stato fatto a 4 mani durante le ferie/vacanze; ed è stata dura, sono intervenute anche le complicazioni dovute ai fusi orari in aggiunta alle solite.
🔴

Calculemus! -- sì, ma forse anche no

Cosa non si trova ontehtoobz! in un tweet oggi questo:

Non so voi ma io  casi come questo mi trovo leibniziano.

Numeri grossi, enormi. Io che sono vecchio subito-subito si accende il *warning* per gli interi [-2^15 : 2^15 - 1]. Poi realizzo che è cosa passata, procedo con la REPL degli usuali (per me) linguaggi preferiti.

E siccome sono pigro invece di mettermi a scrivere codice ricorro a cheat.sh di Igor Chubin, rockz! 💥, devo saperne di più, intanto lo seguo su Twitter.

Racket

$ cht racket factorial
#|
 | traditional recursive factorial and tail-recursive factorial
 | ...https://stackoverflow.com/.../traditional-recursive-factorial-and-
 | tail-recursive-factorial
 |
 | You could use trace (http://docs.racket-
 | lang.org/reference/debugging.html#%28part._.Tracing%29).
 |#

#lang racket

(require racket/trace)

(define factorial
  (lambda (n)
    (if (= n 0)
        1
        (* n (factorial (- n 1))))))
(trace factorial)
(factorial 5)
;; Output:
;; >(factorial 5)
;; > (factorial 4)
;; > >(factorial 3)
;; > > (factorial 2)
;; > > >(factorial 1)
;; > > > (factorial 0)
;; < < < 1
;; < < <1
;; < < 2
;; < <6
;; < 24
;; <120
;; 120

(define factorial-tail
  (lambda (n acc)
    (if (= n 0)
        acc
        (factorial-tail (- n 1)  (* acc n )))))
(trace factorial-tail)
(factorial-tail 5 1)
;; Output:
;; >(factorial-tail 5 1)
;; >(factorial-tail 4 5)
;; >(factorial-tail 3 20)
;; >(factorial-tail 2 60)
;; >(factorial-tail 1 120)
;; >(factorial-tail 0 120)
;; <120
;; 120

; [Greg Hendershott] [so/q/22935169] [cc by-sa 3.0]
$
 
Vado...

$ rkt
Welcome to Racket v6.11.
> (define factorial-tail
    (lambda (n acc)
      (if (= n 0)
          acc
          (factorial-tail (- n 1)  (* acc n )))))
> (define num (* (factorial-tail 20 1) (factorial-tail 7 1)))
> num
12261826121210265600000
> (define den (* (factorial-tail 6 1) (factorial-tail 21 1)))
> den
36785478363630796800000
> (define r (/ num den))
> r
1/3
> (/ 207 621)
1/3
>

OK, avere il tipo razionale è un punto in più per Racket (anzi tutto il Lisp). E per valutare l'ordine di grandezza senza contare le cifre:

> (~r num #:notation 'exponential)
"1.226183e+22"
>

Python

$ cht python factorial
#  Function for Factorial in Python
#
#  Easiest way: math.factorial(x)
#  (https://docs.python.org/library/math.html) (available in 2.6 and
#  above).
#
#  If you want/have to write it yourself, use something like
#  (https://www.artima.com/forums/flat.jsp?forum=181&thread=75931)

def factorial(n):return reduce(lambda x,y:x*y,[1]+range(1,n+1))

#  or something more readable:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

#  As always, Google is your friend ;)
#
#  [schnaader] [so/q/5136447] [cc by-sa 3.0]
$

$ py3
>>> from math import factorial
>>> num = factorial(20) * factorial(7)
>>> num
12261826121210265600000
>>> den = factorial(6) * factorial(21)
>>> den
36785478363630796800000
>>> r = num / den
>>> r
0.3333333333333333
>>> r == (207 / 621)
True
>>>

Node.js --JavaScript

$ cht node factorial
/*
 * What is the fastest factorial function in JavaScript?
 *
 * Lookup table is the obvious way to go, if you're working with natural
 * numbers.
 * To calculate any factorial in real-time, you can speed it with a
 * cache, saving the numbers you've calculated before. Something like:
 */

factorial = (function() {
    var cache = {},
        fn = function(n) {
            if (n === 0) {
                return 1;
            } else if (cache[n]) {
                return cache[n];
            }
            return cache[n] = n * fn(n -1);
        };
    return fn;
})();

/*
 * You can precalculate some values in order to speed it even more.
 *
 * [xPheRe] [so/q/3959211] [cc by-sa 3.0]
 */
$
$ node
> factorial = (function() {
...     var cache = {},
...         fn = function(n) {
.....             if (n === 0) {
.......                 return 1;
.......             } else if (cache[n]) {
.......                 return cache[n];
.......             }
.....             return cache[n] = n * fn(n -1);
.....         };
...     return fn;
... })();
[Function: fn]
> num = factorial(20) * factorial(7)
1.2261826121210266e+22
> den = factorial(6) * factorial(21)
3.6785478363630797e+22
> r = num / den
0.3333333333333333
> r == (207 / 621)
true
>
Però seguire l'istinto a volte non è la cosa migliore, ripensandoci provo...

$ factor 207
207: 3 3 23
$ factor 621
621: 3 3 3 23
ecco c'è un 3 in più nei fattori del denominatore. Se poi provo a sviluppare i fattoriali ottengo:

numeratore
20! * 7! =
    20 * 19 * 18 * 17 * 16 * 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
*
    7 * 6 * 5 * 4 * 3 * 2 * 1
denominatore
21! * 6! =
    21 * 20 * 19 * 18 * 17 * 16 * 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
*
    6 * 5 * 4 * 3 * 2 * 1
eliminando i termini comuni si ha 7 al numeratore e 21 al denominatore.

Per gli altri casi proposti la semplificazione non è così immediata

$ rkt
Welcome to Racket v6.11.
> (/ 17556 55176)
7/22
> (/ 1500475 4741501)
25/79
>
$ factor 17556
17556: 2 2 3 7 11 19
$ factor 55176
55176: 2 2 2 3 11 11 19
$

$ factor 1500475
1500475: 5 5 47 1277
$ factor 4741501
4741501: 47 79 1277
$

entrano in gioco più fattori ma è la stessa cosa.

OK, le fonti, a me l'ha detto math prof che ha rilanciato (patata) Ichiro.

Chiaro, vero? 沢山のいいねとリツイートありがとうございます！

Resterebbe da chiarire quel ポテト. Ma bisognerebbe immergersi nella cultura jap, vedi il caso affine di 吉本 ばなな.
🔴