Numeri primi!

[Gnottino90]

Mi sono imbattutto in questo problema e sinceramente non so come risolverlo..c'è qualcuno che ha un'idea?

Qual è il più piccolo numero intero naturale di quattro cifre (che non cominci con 0) che possiede la seguente proprietà: “se si modifica una qualunque delle sue cifre, non si ottiene mai un numero primo”?

Grazie in anticipo

[jordan]

Viste le sue 4! permutazioni che nondevono iniziare con lo 0, nessuna cifra è 0, ogni cifra è almeno 1, e 1111 funziona visto che è divisibile per 11.

[Il_Russo]

Non credo che per modifiche alle cifre intendesse le permutazioni...

[kwehmucdee]

Viste le sue 4! permutazioni che nondevono iniziare con lo 0, nessuna cifra è 0, ogni cifra è almeno 1, e 1111 funziona visto che è divisibile per 11.

Credo intendesse che puoi cambiare una cifra del numero con un'altra cifra a piacere, quindi per esempio 1111 non va bene perchè cambiando il secondo 1 in 5, diventa 1511 che è primo.

Io dico 1070, bisogna cambiare per forza lo 0 finale perchè cambiando qualsiasi altra cifra sarebbe divisibile per 10, ma non esiste nessuno numero primo di quattro cifre le cui prime tre siano 107. (mentre ce ne sono che iniziano con 100, 101, 102, 103, 104, 105 e 106).

[Spammowarrior]

Mi sono imbattutto in questo problema e sinceramente non so come risolverlo..c'è qualcuno che ha un'idea?

Qual è il più piccolo numero intero naturale di quattro cifre (che non cominci con 0) che possiede la seguente proprietà: “se si modifica una qualunque delle sue cifre, non si ottiene mai un numero primo”?

Grazie in anticipo

la soluzione dovrebbe essere 1070.
si verifica che se si sceglie l'ultima cifra pari, per ottenere un primo bisogna necessariamente cambiare l'ultima. inoltre, se va bene abcd (intendendo la scrittura in cifre) va bene anche abc0.
l'ultima cifra è dunque 0.
inoltre ovviamente l'ultima cifra può avere solo valori dispari.
il problema quindi è modificabile in "quale decina non contiene numeri dispari?"

a questo punto, in piena morte cerebrale, in gara mi crivellerei i primi da mille a millecento, forte del fatto che la caratteristica di questa riformulazione del problema non dovrebbe essere troppo inusuale.

in attesa di qualcuno con una vera soluzione magari ti interessa questa

[Gnottino90]

Grazie delle risposte

Ho capito cosa intendete solo che alcune cose non mi sono chiare!

Ad esempio kwehmucdee: come faccio a sapere che per numeri di quattro cifre che esistono con 101,102,103,104,105,106 ci sono numeri primi?

E Spammowarrior: con - il problema quindi è modificabile in "quale decina non contiene numeri dispari?" - intendi numeri primi dispari?

E in generale come faccio a capire se ad esempio il numero 1001 è primo?Devo provare a dividerlo per tutti i numeri (sensati) fino a 500?

Cmq grazie ancora!! E' solo che i numeri primi diciamo non sono il mio forte..non li ho mai usati molto ._.

[Corneluush]

sono primi: 1009 1021 1039 1049 1051 1061 1087 1093 ad esempio. mentre nella decina da 1070 a 1080 non ce ne sono. Per il 1001: è divisibile per 11 ad occhio e comunque devi provare la divisione per gli interi (primi) minori della radice cioè fino a 31

[Spammowarrior]

Grazie delle risposte

Ho capito cosa intendete solo che alcune cose non mi sono chiare!

Ad esempio kwehmucdee: come faccio a sapere che per numeri di quattro cifre che esistono con 101,102,103,104,105,106 ci sono numeri primi?

E Spammowarrior: con - il problema quindi è modificabile in "quale decina non contiene numeri dispari?" - intendi numeri primi dispari?

E in generale come faccio a capire se ad esempio il numero 1001 è primo?Devo provare a dividerlo per tutti i numeri (sensati) fino a 500?

Cmq grazie ancora!! E' solo che i numeri primi diciamo non sono il mio forte..non li ho mai usati molto ._.

ovviamente sì, mi sono perso a metà della frase.
secondo me in un caso del genere però, invece che provare ogni singolo numero per verificarne la divisibilità (poichè dividere per 29 non è affatto divertente ) io come ho detto userei il crivello di eratostene, che è un algoritmo per calcolare i numeri primi...
comunque anche trovare la divisibilità di tutti i numeri tentando a dividere fino alla radice quadrata ti porta comunque al risultato, magari privandoti della tua sanità mentale nel frattempo

[Gnottino90]

sono primi: 1009 1021 1039 1049 1051 1061 1087 1093 ad esempio. mentre nella decina da 1070 a 1080 non ce ne sono. Per il 1001: è divisibile per 11 ad occhio e comunque devi provare la divisione per gli interi (primi) minori della radice cioè fino a 31

Ma quei numeri primi li dovrei sapere a memoria o li hai ricavati?
E..uhm..perchè basta provare a dividere per i numeri fino alla radice quadrata?

Ora provo a cercare il crivello di eratostene!

[Spammowarrior]

sono primi: 1009 1021 1039 1049 1051 1061 1087 1093 ad esempio. mentre nella decina da 1070 a 1080 non ce ne sono. Per il 1001: è divisibile per 11 ad occhio e comunque devi provare la divisione per gli interi (primi) minori della radice cioè fino a 31

Ma quei numeri primi li dovrei sapere a memoria o li hai ricavati?
E..uhm..perchè basta provare a dividere per i numeri fino alla radice quadrata?

Ora provo a cercare il crivello di eratostene!

l'idea dietro alla radice quadrata è che se un numero è divisibile per un primo maggiore della radice quadrata, è divisibile anche per un numero minore: infatti il risultato che ti esce dividendolo per quel primo è minore della radice quadrata.

[Gnottino90]

Non capisco una cosa: perchè se è divisibile per un numero maggiore della radice quadrata allora è divisibile anche per un numero minore?

Cmq ho capito come funziona il crivello..quindi dovrei applicarlo senza sapere la soluzione fino ad esepio a n=1100? Viene un po' lunghetto ._.

[Spammowarrior]

nel tuo caso il crivello funzionerebbe così:
ti scrivi i numeri dispari da 1000 a 1100, elimini i multipli di 3, di 5, di 7 e così via fino al 31, e poi guardi quelli che ti sono rimasti, che sono i primi compresi tra 1000 e 1100.
lunghino ma nemmeno troppo, 5-10 minuti te la sbrighi.
in un problema come questo in assenza di idee è una soluzione che vale la pena considerare.


comunque prendiamo un numero X.
a divide X, quindi X/a=b

se a è maggiore della radice quadrata di x, allora b sarà minore, e quindi ha un divisore minore della radice. quindi se X ha divisori maggiori della radice, ce ne ha anche minori.

[Gnottino90]

Ahhh!Capito!!Che scemo che sono >.<
Tutto quadra allora!!

Ora provo a rifarlo per vedere che ho veramente capito!

Grazie mille per l'aiuto!!Cmq SpammoWarrior se sei ancora qui..secondo te cosa potrei fare oltre agli esercizi per prepararmi ad esempio alla gara della Bocconi?il fatto è che anche se faccio gli esercizi poi è difficile che siano simili a questi e quindi magari non serve a niente farli..

[Spammowarrior]

Ahhh!Capito!!Che scemo che sono >.<
Tutto quadra allora!!

Ora provo a rifarlo per vedere che ho veramente capito!

Grazie mille per l'aiuto!!Cmq SpammoWarrior se sei ancora qui..secondo te cosa potrei fare oltre agli esercizi per prepararmi ad esempio alla gara della Bocconi?il fatto è che anche se faccio gli esercizi poi è difficile che siano simili a questi e quindi magari non serve a niente farli..

la cosa importante è il metodo che usi, non tanto il problema in sè.

vi sono alcuni tipi di approcci standard ai problemi, oppure soluzioni furbe a problemi comuni che probabilmente non ti verrebbero in mente in gara: solo per citarne alcuni che non conoscevo prima di affrontarli in un esercizio ci sono lo sviluppo di un solido su un piano, controllare le divisibilità e le congruenze, provare a mano i casi più semplici per vedere se c'è un elemento ricorrente.

in poche parole, ciò che impari risolvendo esercizi non è nulla di incredibile, ma fa comodo esserselo preparato a casa, piuttosto che doverselo inventare in una gara (con il problema sia del tempo che dell'eventuale nervosismo)


per quanto riguarda che problemi fare, conviene sempre provare i problemi delle precedenti edizioni della gara che si tenta, o in alternativa problemi di livello simile (indicativamente, cesenatico ha già dei problemi belli difficilotti, mentre le gare di febbraio dovrebbero essere più o meno tutte fattibili, con un po' di immaginazione, e sbattendoci su la testa un po')

[Gnottino90]

Capisco..infatti sto provando gli esercizi delle edizioni precedenti e di cesenatico!Però spesso io per trovare la soluzione uso metodi lunghi che cambiano da esercizio ad esercizio..il fatto è che io credo di essere abbastanza portato per queste cose ma non avendo mai fatto niente del genere negli anni delle superiori (soprattutto perchè sono stato in un liceo di una paesino piccolo e quindi non mi hanno nemmeno spronato più di tanto..anzi direi per niente )..e quindi le varie tecniche mi mancano e sono sicuro che ci sono molti modi di fare gli esercizi più velocemente di come li faccio io!
E' solo che mi sono svegliato troppo tardi e ora è difficile recuperare e capire come farli