Riemann 1

Un problemino di programmazione per i patiti:

Quanti sono i numeri primi minori od uguali ad un numero x?

Chiamiamo P(x) la funzione che calcola tale numero.

Per esempio P(1)=0, P(2)= 1, P(3)=2, P(4)=2 ecc.

Dopo aver programmato una funzione che calcola P(x), farsene una tabella e fare qualche ipotesi su come potrebbe essere fatta questa funzione (magari trovarla!)

Ricchi premi

Advertisements
Questa voce è stata pubblicata in Algoritmi, Aritmetica, Informatica, Matematica, Programmazione e contrassegnata con , , , . Contrassegna il permalink.

29 risposte a Riemann 1

  1. bobcarr ha detto:

    @edoardo

    come puoi vedere, il difficile è comunicare le cose, più che pensarle, in particolare in matematica; dunque vediamo come l’avrei detto io:

    per assurdo: supponiamo che x non abbia divisori fino a y, quindi: \displaystyle x = yz con \displaystyle y > \sqrt{x}
    allora \displaystyle z < \sqrt{x}
    ma allora z sarebbe un divisore di x e lo avrei già trovato prima: assurdo.

  2. bobcarr ha detto:

    dunque: il problema è stato risolto al 90%

    calcolata la funzione P(x), grafico della medesima
    non sono state fatte considerazioni interessanti sulla forma del grafico

    @filippo 0.3 crediti per il programma/grafico
    @edoardo 0.3 crediti per la dimostrazione del teorema che però non è ancora chiara

    il post è chiuso, a presto riemann 2

  3. bobcarr ha detto:

    @filippo

    interessante il grafico: sembra fatto a scale, perché?

    i gradini delle scale sembrano progressivamente più larghi, che vuol dire?

    • Filippo Bisconcin ha detto:

      Se i gradini sono più larghi significa che i numeri primi diventano più rari da trovare man mano che saliamo coi numeri e quindi le variazioni nel contatore di numeri primi diventano sempre più distanti

  4. bobcarr ha detto:

    aggiustiamo il teorema:

    per stabilire se un numero è primo basta dividerlo per tutti i primi minori o uguali alla sua radice quadrata

    dimostrazione?

    • bobcarr ha detto:

      ancora in attesa della dimostrazione

      • 1. Se un numero ( X ) è divisibile per un numero ( Y ) è anche divisibile per il risultato della divisione ( Z, Z=X/Y ).
        2. Se si continua a controllare se il numero è divisibile per Y, quando Y supererà Z, Y inizierà a prendere i valori di Z, valori che abbiamo già controllato per 1.
        3. se Y=Z Y=sqrt(X)* quindi basta controllare fino a sqrt(X)

        * X/Y=Z, Z=Y => X/Y=Y X=Y^2 => X=sqrt( Y )

        • bobcarr ha detto:

          non capisco

          in particolare 1. non mi pare vero

        • Siano X,Y numeri interi. Se X è divisibile per Y allora X/Y = Z intero
          Se dividiamo X/Z il risultato è Y, ed essendo intero allora X è divisibile per Z

        • bobcarr ha detto:

          non mi sembra chiaro lo stesso

        • Da un altro punto di vista: mettiamo che un numero X è divisibile per un numero Y maggiore di sqrt(x), dato che è divisibile restituisce un numero intero, Z, questo numero sarà minore di sqrt(x)*. Quindi non serviva controllare per Y che andava dopo a sqrt(x) ma bastava controllare precedentemente per Z. Sqrt(x) è il limite fino a cui controllare perchè è l’ultimo valore prima che i divisori si “ripetano”

          *X è dato dalla moltiplicazione dei due fattori sqrt(x) e sqrt(x) se uno diventa Y e quindi aumenta l’altro deve per forza diminuire per dare sempre X come risultato.

  5. Filippo Bisconcin ha detto:

    Ho fatto in modo che il programma crei un file .xls con due colonne di dati (numero e numeri primi); poi il programma elabora un grafico

    Immagine: http://oi55.tinypic.com/emz55.jpg

    • bobcarr ha detto:

      il grafico è già interessante
      come si legge?
      se voglio sapere P(10) come faccio?

    • Filippo Bisconcin ha detto:

      Sull’asse delle ascisse si leggono i valori che ho preso fino a 100 (per starci nel grafico) mentre sull’asse delle ordinate si legge la quantità di numeri primi minori o uguali della cifra presa in considerazione

  6. fatto, provo a fare un grafico

  7. Ma il 10 non ha come divisore il 5 che è maggiore della radice di 10?
    Non è che si può cercare fino alla radice quadrata di quel numero perché se è divisibile per 5 vuol dire che era già prima divisibile per il 2?
    Quindi non è che che un numero intero N non può avere divisori maggiori della sua radice quadrata, ma che per testare se ha divisori si può controllare fino alla sua radice quadrata.

  8. Filippo Bisconcin ha detto:

    ho trovato un teorema secondo cui “un numero intero N non può avere divisori maggiori della sua radice quadrata” e sono riuscito a are un programma che calcola tutti i numeri primi minori o uguali ad un numero, adesso faccio quello che calcola il numero di numeri primi per una serie di numeri

I commenti sono chiusi.