Cliquez pour afficher

301-->3+0+1 =4
et  1 ;7;43; 301 --->4 diviseurs

 Cliquez pour afficher

ferai un algorithme en commençant par 9876543210 et en descendant ...

 Cliquez pour afficher

9780--->24 diviseurs et +9+7+8+0=24 pour somme

 Cliquez pour afficher

9876025314 --->total  45
et 45 diviseurs.

 Cliquez pour afficher

que le plus grand doit ne pas avoir de 1...

je cherche dans la bande 987654320  

 Cliquez pour afficher

985 076 432 de total 44 avec 44 diviseurs (liste si

 Cliquez pour afficher

On a vu plus haut qu'il était absurde de tester les 10 chiffres...
Je pense avoir trouvé avec 9 donc dans cette tranche,il y a  fact 9
soit 362 880 combinaisons possibles.

 Cliquez pour afficher

on n'a pas montré qu'avec 10 chiffres c'était absurde mais que nécessairement c'est un carré...

 Cliquez pour afficher

9614783025 comporte bien les dix chiffres donc 45
et possède 45 diviseurs.

 Cliquez pour afficher

8 135 679 204
7 854 036 129
7 351 862 049
6 154 873 209
5 982 403 716
3 791 480 625
3 428 570 916

 Cliquez pour afficher

Si , ne peut valoir 45 que si tous ses facteurs sont impairs, i.e si tous les sont pairs, i.e si n est un carré parfait.

Comme a exactement 10 chiffres,
, et donc .

On peut encore raffiner: les diviseurs de sont 1, 3, 5, 9, 15, 45.
Il n'y a qu'un nombre fini de moyens d'obtenir 45 avec des multiplications, à l'ordre près des facteurs
45 = 1*45
45 = 3*15
45 = 5*9
45 = 3*3*5

Le premier cas correspond aux entiers de la forme .
Le deuxième, aux entiers de la forme , i.e
Le troisième aux entiers de la forme , i.e
Le dernier aux entiers de la forme , i.e


On peut exclure d'office le premier cas, puisque le plus petit tel candidat est , qui est largement hors limites.

Le deuxième cas parle de lui-même. On aura q^7 >= 10^5/2 dès que q >= 4. Les seules possibilités pour q sont donc 2 et 3.
Quand q = 2, on ne parcourra que les multiples de 128 entre 31623 et 10^5 (il y en a environ 500). Cela ne nécessite que de connaitre les nombres premiers entre 248 et 781.
Quand q = 3, les multiples de 2187 et il n'y en a qu'une trentaine. Cela ne nécessite que de connaitre les nombres premiers entre 15 et 45.

Le troisième cas revient à chercher les nombres . Là encore bruteforce léger. Comme ci-dessus, on peut si on veut faire comme au cas 2, en remplacant les q7 par des q2 pour q=2,3,5,7,11 et en mettant au carré et pas à la puissance 4.

Même chose pour le dernier cas.


Petit code en Go pour changer un peu de python
La partie Eratosthene peut s'avérer difficile à comprendre. De même les opérations de tri et d'unicisation sont bien moins triviales qu'en Python, mais pas bien difficiles (ni optimales )

package main

import (
	"fmt"
	"math/bits"
	"sort"
	"strconv"
)


type sortRunes []rune

func (s sortRunes) Less(i, j int) bool {
    return s[i] < s[j]
}

func (s sortRunes) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func (s sortRunes) Len() int {
    return len(s)
}

func SortString(s string) string {
    r := []rune(s)
    sort.Sort(sortRunes(r))
    return string(r)
}



func primes_from_sieve(sieve []uint, offset uint, skip int) []uint {
	
	nb_primes := skip
	for _, v := range sieve {
		nb_primes += bits.OnesCount(v)
	}

	primes := make([]uint, nb_primes)
	idx := skip

	for s,v := range sieve {
		s128_3 := (uint(s) << 7) + 3 + offset
		for j := uint(0); v != 0; j++ {
			if v&1 != 0 {
				// p = 2*(64*s + j) + 3 = 128s + 2j + 3
				p := s128_3 + (j << 1)
				primes[idx] = p
				idx++
			}
			v >>= 1
		}
	}
	return primes
}

func Eratosthene(n uint) ([]uint, []uint) {
	switch {
		case n == 2:
			return []uint{},[]uint{2}
		case n <= 4:
			return []uint{1}, []uint{2, 3}
		case n <= 6:
			return []uint{3}, []uint{2, 3, 5}
	}

	N := (((n + (n&1) - 1) - 3) >> 1) + 1 // le nombre d'entiers à cribler. Il est forcément >= 2 grâce au switch
	len_sieve := N >> 6 // on les groupe par 2^6 = 64
	if N&63 != 0 {
		len_sieve++
	}
	//fmt.Println(N, len_sieve, 2*(N-1)+3)

	// initialiation du crible
	sieve := make([]uint, len_sieve) // bit 1 ssi nombre premier
	sieve[0] = 3 // 3 et 5 sont premiers

	for i := uint(2); i != N; i++ {
		//j = 2*i + 3 = 5i - 3(i-1)
		// j % 3 = 2(i%3) mod 3 est nul ssi i%3 est nul parce que 2*0 = 0, 2*1 = 2 et 2*2 = 4 = 1 dans Z/3Z
		// j % 5 est nul ssi 3(i-1) % 5 est nul. 3*(1-1) = 0, 3*(2-1) = 3, 3*(3-1) = 6 = 1, 3*(4-1) = 9 = 4 et 3*(5-1) = 12 = 2 dans Z/5Z
		// donc j% 5 == 0 ssi i%5 == 1

		// set seulement si j ni multiple de 3 ni de 5
		if i%3 != 0 && i%5 != 1 {
			sieve[i >> 6] |= 1 << (i&63)
		}
	}
	

	// erathostene
	for i := uint(2); i != N; i++ { // on commence à 2*2 + 3 = 7
		// recherche du prochain premier
		for i != N && (sieve[i>>6] >> (i&63))&1 == 0 {
			i++
		}
		if i >= N {
			break
		}

		p := (i << 1) + 3
		p2 := p*p
		if p2 > n {
			break
		}

		//fmt.Println("sieving for", p)
		p <<= 1 // seuls les impairs nous intéressent, on fera donc des pas de 2*p : p^2 + 2kp = p(p+2k) = p^2 = 1 mod 2
		for q := p2; q <= n; q += p { 
			q_i := (q-3) >> 1
			sieve[q_i >> 6] &= ^( 1 << (q_i&63) )
		}


	}

	primes := primes_from_sieve(sieve,0,1)
	primes[0] = 2


	//fmt.Println(len(fmt.Sprintf("%b", sieve[0])))
	fmt.Printf("eratos: %v primes found, sieve length %v\n", len(primes), len(sieve))
	return sieve, primes
}


func distinct_digits(n uint) bool {
	s := SortString(strconv.FormatUint(uint64(n),10))
	return s == "0123456789"
}


func candidates_pq7(q7 uint, primes, c []uint) []uint {
	for _, p := range primes {
		m := p*q7

		if m < 31623 {
			continue
		}
		if m >= 100_000 {
			break
		}
		
		
		n := m*m
		//fmt.Println(n)
		if distinct_digits(n) {
			c = append(c, n)
		}
	}

	return c
}

func candidates_pq2(primes, c []uint) []uint {
	for _, q := range primes {
		q2 := q*q
		for _, p := range primes {
			m := p*q2

			if m < 178 {
				continue
			}
			if m > 316 {
				break
			}

			n := m*m
			n = n*n // puissance 4
			//fmt.Println(n)
			if distinct_digits(n) {
				c = append(c, n)
			}
		}
	}

	return c
}

func candidates_pqr2(primes, c []uint) []uint {
	for _,r := range primes {

		if r > 158 {
			break // sinon 4r^2 > 10^5
		}

		r2 := r*r
		for _, q := range primes {
			qr2 := q*r2

			if qr2 > 50_000 { // sinon 2qr2 > 10^5
				break
			}

			for _, p := range primes {
				m := p*qr2

				if m < 31623 {
					continue
				}
				if m >= 100_000 {
					break
				}
				
				
				n := m*m
				//fmt.Println(n)
				if distinct_digits(n) {
					c = append(c, n)
				}
			}
		}
	}

	return c
}

func unique(c []uint) []uint {
	m := make(map[uint]bool)
	d := []uint{}
	for _, x := range(c) {
		if _, ok := m[x] ; !ok {
			m[x] = true
			d = append(d, x)
		}
	}
	return d
}


func uint_int(c []uint) []int {
	d := make([]int, len(c))
	for i, x := range c {
		d[i] = int(x)
	}
	return d
}


func main() {
	_, primes := Eratosthene(100_000)
	c := []uint{}

	c = candidates_pq7(128, primes, c)
	c = candidates_pq7(2187, primes, c)

	//fmt.Println("----------------")

	c = candidates_pq2(primes, c)

	//fmt.Println("----------------")

	c = candidates_pqr2(primes, c)

	uc := uint_int(unique(c))
	sort.Sort(sort.IntSlice(uc))

	fmt.Println(uc)

}

 Cliquez pour afficher

1278563049
2076351489
3428570916
3791480625
5982403716
6154873209
7351862049
7854036129
8135679204
9614783025

 Cliquez pour afficher

207635489 et 1278563049. (mauvaise recopie)