Farey Sequence Manipulation

Question

quindi sono estremamente nuovo in Mathematica e attualmente sto realizzando un progetto che prevede il calcolo di una funzione specifica delle frazioni di Farey. Viene dato un intervallo$I: (0,\alpha)$, Voglio calcolare il numero di coppie distinte $i$,$j$ st $i-j$ $\in I$in un elenco normalizzato di frazioni di farey. Il fattore di normalizzazione qui è$\frac{1}{|F_d-1|}$, dove $|F_d|$è la dimensione dell'elenco delle frazioni tariffarie con denominatore d. Quindi, ad esempio con il denominatore 5, l'elenco normale delle frazioni di Farey è$FareySequence[5]$, mentre l'elenco normalizzato è $|F_d-1|(FareySequence[5])$.

Di seguito è riportato il mio tentativo di contare il numero di coppie distinte $i,j$ che fanno parte di una sequenza di Farey normalizzata tale che $i-j<1$, dove $i>j$. Qui, lo sto contando in base alle frazioni con denominatore 1000. Ci sono 304193 tali frazioni. Ho usato un contatore, dove viene aggiunto un conteggio ogni volta che c'è una coppia la cui differenza è inferiore a 1. Tuttavia, ogni volta che lo eseguo, il programma non valuta mai. Qualsiasi aiuto sarebbe apprezzato.

count = 0

For[i = 1, i < 304193, i++,
 
For[j = 1, j < i, j++,
 
 if[(304193 FareySequence[1000, i]) - (304193 FareySequence[1000, 
        j]) < 1, count ++, count = count ]
  
]
 ]

Print[count]

Answer 1

Ecco la soluzione che funziona rapidamente:

FareySequence[1000] è lungo solo 304193 elementi, abbastanza breve da poter essere salvato in memoria, quindi calcola la sequenza una volta e accedi agli elementi per accelerare.

fs = 304193*FareySequence[1000];

Quindi nota che gli elementi di FareySequence aumentano in modo monotono, quindi se prendi l'elemento fs [[i]] e l'elemento precedente, fs [[i-1]] ha una distanza padre di 1 da f [[i]] non Non è necessario testare nessuno degli elementi all'inizio della sequenza. Quindi, invece di testare j da 0 a i, prova j da i-1 in giù e interrompi ogni volta che la tua condizione non è soddisfatta.

For[
 i = 1, i < 304193, i++,
 For[j = (i - 1), j > 0, j--,
  If[(fs[[i]] - fs[[j]]) < 1, count++, Break[]]
  ];
 ]

Print[count]

232074

Questo si completa in poco meno di 2 secondi.

Ecco una soluzione più matematica ("funzionale") che non funziona molto rapidamente:

Prima scrivi una funzione che accetta una sequenza, quindi la usa TakeWhileper attraversare tutta la sequenza tranne l'ultimo elemento usando l'ultimo elemento per il confronto e interrompendo se la differenza tra i due elementi è maggiore di lim, Lengthconta la lunghezza di questa lista.

countBelowWithin[seq_, lim_:1] := 
  Length@TakeWhile[Reverse[Most[seq]], Last[seq] - # < lim &];

Quindi utilizzare Tableper prendere le sottosequenze dell'intera sequenza e passarle a countBelowWithin. La tabella risultante sarà il numero di elementi che hanno soddisfatto i criteri per quella sottosequenza, quindi Totalaggiunge quelli per un numero totale di elementi che soddisfano i criteri.

With[
 {a = fs[[;; 10000]]},
 Total[
  Table[
   countBelowWithin[a[[;; i]]]
   , {i, 2, Length@a}
   ]
  ]
 ]

Uso il Withper isolare una parte della sequenza fsa scopo di test.

Molto spesso la soluzione funzionale può essere più rapida, in questo caso non lo è. Spesso è meno soggetto a errori poiché puoi pensare in concetti più grandi rispetto agli indici. In questo caso probabilmente dovresti pensare un po 'di più se volessi una soluzione funzionale che funzionasse in un tempo ragionevole.

Se siete interessati a saperne di più, c'è un sacco di fondamenti di qui Partvale a dire ...[[;;]], Table, TakeWhile. Comincerei semplicemente a leggere i documenti su questa roba, così come i link forniti da altri poster.

Answer 2

Più un commento esteso che una risposta ...

Se riduci il limite del tuo iiteratore a qualcosa di piccolo, ad esempio 10piuttosto che 304193, il codice corretto (" IF" invece di " if") sembra funzionare bene.

Prova quanto segue:

count = 0;
For[i = 1, i < 10, i++,
 For[j = 1, j < i, j++,
  If[
   (304193 *FareySequence[1000, i]) - (304193 * FareySequence[1000, j]) < 1,
   count++, count = count]]]
Print[count]

quali uscite: 18

Sembra che l'impostazione del limite iterativo di iat 304193produca un numero enorme di valutazioni nei Forcicli annidati .

Penso che tu possa produrre il tuo risultato in molto meno tempo con i mezzi di "programmazione funzionale" (la vera forza di Mathematica) piuttosto che con il looping iterativo.

La semplice mappatura IFdell'affermazione attraverso gli intervalli appropriati probabilmente acquisirà una grande velocità. Quindi fai un "conteggio" separato delle istanze che desideri identificare.

Ci penserò su più tardi nel corso della giornata e tornerò se nessun altro ha ancora fornito una risposta.