QUATTRO

Un problemino di programmazione per tutti (e per nessuno)

Un numero è TRIANGOLARE se è la somma di  tutti i numeri precedenti:

es:

  • 1=1
  • 1+2=3
  • 1+2+3=6
  • 1+2+3+4=10
  • ecc
se scompongo in fattori i numeri triangolari (compresi 1 e il numero stesso) ottengo:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

Osserviamo che 28 è il primo numero triangolare che ha più di 5 divisori.

Problema: qual’è il primo numero triangolare che ha più di 500 divisori?

Stesse caratteristiche degli altri problemi.

(1 credito for this problem, the code is mandatory)

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

21 risposte a QUATTRO

  1. bobcarr ha detto:

    va be ma si può vedere sti codici?

    • Filippo Bisconcin ha detto:

      Dim d = 1000

      Function tr(ByVal o As Double)
      Return (o * (o + 1)) / 2
      End Function

      Function fattori(ByVal numero As Integer)
      Dim nu = 0
      Dim s = Math.Sqrt(numero)
      For a = 1 To s
      If numero Mod a = 0 Then
      nu += 1
      If a numero / a Then nu += 1
      End If
      Next
      Return nu
      End Function

      **********Main**********
      Dim pos = 1
      While fattori(tr(pos)) < d
      pos += 1
      End While
      **********Main**********

  2. baldassin ha detto:

    Scusate il ritardo, ma dopo una nuova installazione dell’os di nuovo il maledetto ‘binary not found’ di eclipse. La soluzione dovrebbe essere 76576500 con ben 576 divisori. Il nuovo metodo devo ancora provarlo.

  3. bobcarr ha detto:

    una soluzione in linguaggio J:

    foo=:[: */ 1: + [: +/"1 =@q:
    {.(500 <; foo 0 )#t =+ /\ > : i.13000

    ovviamente l'ho copiata e non ci capisco niente
    tempo di esecuzione: istantaneo

  4. bobcarr ha detto:

    un suggerimento fondamentale:

    un numero qualsiasi si scompone in fattori primi in questo modo:
    28 = 4*7 = 2^2*7 quindi il numero dei suoi divisori è :
    i divisori di 4 : 1, 2 ,4 quindi l’uno più un fattore per ogni esponente= 1+2 = 3 in tutto; i divisori di 7 sono 1 e 7 quindi 2 in totale; allora il numero di divisori di 28 è = 3*2 = 6
    se avessimo una funzione D(x) che ci da il numero dei divisori basterebbe solo generare i numeri triangolari e siamo a posto: giusto?

  5. Filippo Bisconcin ha detto:

    nel calcolo di 200 numeri utilizzando le procedure trova_fattori(numero) e trangolare(numero) si risparmia un misero secondo

  6. bobcarr ha detto:

    una soluzione in julia:

    lim=2000000
    tot=5
    n=5

    while n <= lim
    if isprime(n)
    tot+ = n
    end
    n+ = 2
    end
    println(tot)

    impiega meno di 1 secondo (imac i7)

    • baldassin ha detto:

      E’ il 3 vero?
      Questo ci mette troppo, ho anche migliorato l’algoritmo visto che mi son accorto che ripetevo ad ogni ciclo le stesse identiche somme (penso fosse quello che mi diceva il bisco), ma il tempo rimane lo stesso, circa mezz’ora. Per trovare i triangolari più di così non penso si possa fare, forse c’è un modo più veloce per calcolare i divisori? (vado da 2 a n/2 e provo a dividerli tutti).

    • Filippo Bisconcin ha detto:

      idem…parto da 1 e vado fino a n/2 aggiungendo poi 1 per se stesso
      l’altra sera ho trovato come ottimizzare i numeri trinagolari

    • bobcarr ha detto:

      si ho sbagliato post

  7. Filippo Bisconcin ha detto:

    col mio algoritmo ci mette troppo tempo😦

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...