Niveau énigmes

Nombres complétement premiers

Posté par
dpi 05-09-23 à 09:00

Bonjour à tous ,
Dans l'univers des premiers
On va dire qu'un nombre est complètement premier quand
a) il est bien sûr premier
b)quand tous ses chiffres sont premiers .
Exemple 23

Question
Combien y a t-il de nombres complètement premiers < 100 000

Posté par re : Nombres complétement premiers 05-09-23 à 09:25

Salut, j'en compte

Cliquez pour afficher

que voici:

Cliquez pour afficher

Posté par re : Nombres complétement premiers 05-09-23 à 11:16

Bonjour Littlefox,
Je savais bien que tu aimerais
En attendant les autres, je cherche pour <1000 0000

Posté par re : Nombres complétement premiers 05-09-23 à 13:23

Suite,

La raréfaction se poursuit:

Cliquez pour afficher

Posté par re : Nombres complétement premiers 05-09-23 à 15:52

Code python sans itertools ou optimisation

Cliquez pour afficher


def eratos(n):
	if n < 2:
		return;
	if n == 2:
		yield 2
		return;

	n -= 1 - (n&1)
	m = n - 3 >> 1
	sieveb = [True] * (m + 1)

	for p in range(3, n+1, 2):
		if p * p > n:
			break;
		if not sieveb[p - 3 >> 1]:
			continue;

		for q in range(p * p, n+1, 2 * p):
			i = q - 3 >> 1
			sieveb[i] = False

	yield 2
	yield from (3 + 2 * i for i in range(m+1) if sieveb[i])

def is_prime(n, sieve):
	return n == 2 or n in sieve

def with_prime_digits(nb_digits):
	if nb_digits < 2:
		yield from (2,3,5,7)
		return;

	p = 10 ** (nb_digits - 1)
	for r in with_prime_digits(nb_digits - 1):
		yield from (u*p + r for u in (2,3,5,7))

def super_primes(nb_digits, sieve):
	if nb_digits < 2:
		return 4

	primes = (
		filter(
			lambda x: is_prime(x, sieve), with_prime_digits(d)
		)
		for d in range(2, nb_digits+1)
	)

	return 4 + sum(len(set(p)) for p in primes)


nb_digits = 7
n = (10**nb_digits - 1) // 9 * 7
sieve = set(eratos(n))

print(super_primes(nb_digits, sieve))

La même chose en Rust et toujours sans optimisation

Cliquez pour afficher


fn with_digits(nb_digits: u32) -> Vec<u128> {
    if !(2..=38).contains(&nb_digits) {
        return vec![2u128, 3, 5, 7];
    }

    let p = 10_u128.pow(nb_digits - 1);
    with_digits(nb_digits - 1)
        .into_iter()
        .flat_map(|r| [2u128, 3, 5, 7].into_iter().map(move |h| h * p + r))
        .collect()
}

fn is_prime(n: u128, sieve: &[u128]) -> bool {
    n == 2 || sieve.binary_search(&n).is_ok()
}

fn eratos(mut upper_bound: u128) -> Vec<u128> {
    upper_bound = (isize::MAX as u128).min(upper_bound);

    if upper_bound < 2 {
        return vec![];
    }

    if upper_bound == 2 {
        return vec![2];
    }

    upper_bound -= 1 - (upper_bound & 1);

    println!("{upper_bound}");

    let m = ((upper_bound - 3) >> 1) as usize;
    let mut sieveb = vec![true; m + 1];

    for p in (3u128..).step_by(2) {
        if p * p > upper_bound {
            break;
        }
        if !sieveb[((p - 3) >> 1) as usize] {
            continue;
        }
        for q in (p * p..=upper_bound).step_by(2 * p as usize) {
            let i = (q - 3) >> 1;
            sieveb[i as usize] = false;
        }
    }

    std::iter:nce(2)
        .chain((0..=m).filter_map(|i| sieveb[i].then_some(3 + 2 * i as u128)))
        .collect()
}

fn main() {
    let nb_digits = 7;
    let sieve = eratos((10u128.pow(nb_digits) - 1) / 9 * 7);
    println!("{}", sieve.len());

    let super_primes: Vec<_> = (1..=nb_digits)
        .flat_map(|n| with_digits(n).into_iter().filter(|&p| is_prime(p, &sieve)))
        .collect();

    println!("{}", super_primes.len());
}

(le smiley qui est venu s'inviter dans le code est à remplacer par :o pour donner std::iter::once

essayable ici :

Les valeurs pour 10^6, 10^7, 10^8, et 10^9 sont respectivement

Cliquez pour afficher

Posté par re : Nombres complétement premiers 05-09-23 à 15:54

Soit P(n) le nombre de nombres premiers plus petits que n, C(n) le nombre de nombres complètement premiers plus petits que n et D(n) le nombre de nombres composés de digit premiers plus petits que n.

C(n)/n diminue rapidement avec n, tout comme les nombres premiers
C(n)/P(n) diminue moins vite mais diminue
C(n)/D(n) diminue encore moins vite.

Cliquez pour afficher

n             P(n)     D(n)    C(n)     C(n)/n   C(n)/P(n)   C(n)/D(n)
10               4        4       4    40.000%    100.000%    100.000%
100             25       16       8     8.000%     32.000%     50.000%
1000           168       64      23     2.300%     13.690%     35.938%
10000         1229      256      61     0.610%      4.963%     23.828%
100000        9592     1024     189     0.189%      1.970%     18.457%
1000000      78498     4096     578     0.058%      0.736%     14.111%
10000000    664579    16384    1903     0.019%      0.286%     11.615%

Posté par re : Nombres complétement premiers 05-09-23 à 16:50

Juste pour le sport, ma version rust

Cliquez pour afficher

fn is_prime(n: u64) -> bool {
    if n == 2 {
        return true;
    }
    if n % 2 == 0 {
        return false;
    }
    let mut d = 3;
    while d * d <= n {
        if n % d == 0 {
            return false;
        }
        d += 2
    }
    true
}

fn complete_numbers_up_to(n: u64) -> Vec<u64> {
    let digits = vec![2, 3, 5, 7];
    let mut new_complete_numbers = digits.clone();
    let mut complete_numbers = digits.clone();

    while complete_numbers.last().unwrap() + 1 < n {
        new_complete_numbers = new_complete_numbers
            .iter()
            .flat_map(|&c| digits.iter().map(move |d| c * 10 + d))
            .collect();
        complete_numbers.extend(&new_complete_numbers);
    }

    while *complete_numbers.last().unwrap() >= n {
        complete_numbers.pop();
    }

    complete_numbers
}

fn complete_primes_up_to(n: u64) -> Vec<u64> {
    complete_numbers_up_to(n)
        .into_iter()
        .filter(|&c| is_prime(c))
        .collect()
}

fn main() {
    println!("{:}", complete_primes_up_to(1000_000_000).len());
    // println!("{}", complete_primes_up_to(1000000));
}

On peut remplacer is_prime par num_prime::nt_funcs::is_prime64, malheureusement cette librairie n'est pas disponible dans le playground.

Posté par re : Nombres complétement premiers 06-09-23 à 07:25

Bravo à vous deux .
Remarque dans l'univers des pcp (premiers complètement premiers) il n'y a que 4 opérations possibles :
2+3=5 et 5-3=2
2+5=7 et 7-5=2

Ce topic

Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Fiches de maths

Fiches de mathématiques

Rechercher

Espace membre

Zone membre

Pas de compte ?
Je m'inscris

Changer d'île

Cours et Exercices de maths

Forum de maths

college

lycee

Outils de maths

Pages les plus populaires

Nombres complétement premiers

Seuls les membres peuvent poster sur le forum !

Ce topic

Fiches de maths