Inscription / Connexion Nouveau Sujet
Niveau 3 *
Partager :

Enigmo 300 : Six pour un sixième

Posté par
jamo Moderateur
02-06-13 à 11:11

Bonjour tout le monde,

pour commencer, je vous laisse vérifier l'égalité suivante :

\frac{1}{6} = \frac{1}{12} + \frac{1}{24} + \frac{1}{48} + \frac{1}{84} + \frac{1}{168} + \frac{1}{336}

La fraction \frac{1}{6} est décomposée en somme de 6 fractions unitaires toutes différentes.
Je rappelle qu'une fraction unitaire est une fraction dont le numérateur est égal à 1, et le dénominateur est un entier strictement positif.

En additionnant les 6 dénominateurs, on obtient 672.

Je sens que vous avez deviné la question ...

Question : Décomposez la fraction \frac{1}{6} en une somme de 6 fractions unitaires toutes différentes, de telle sorte que la somme des 6 dénominateurs soit la plus petite possible.

Pour la réponse, vous me donnerez :
- la décomposition
- et la somme des 6 dénominateurs.

Si vous trouvez plusieurs décompositions qui donne la même somme des dénominateurs, vous pourrez ne donner qu'une seule décomposition.

Bonne recherche !

Enigmo 300 : Six pour un sixième

Posté par
littleguy
re : Enigmo 300 : Six pour un sixième 02-06-13 à 11:31

perduBonjour,

Avant de partir au soleil, je jette :

1/18 + 1/24 + 1/36 + 1/60 + 1/72 + 1/90

Somme : 300

Posté par
Nofutur2
re : Enigmo 300 : Six pour un sixième 02-06-13 à 11:52

gagné Je trouve

1/6 = 1/26 + 1/30 + 1/36 + 1/39 + 1/45 + 1/52
avec un total des dénominateurs de 228.

Posté par
panda_adnap
re : Enigmo 300 : Six pour un sixième 02-06-13 à 12:07

gagnéBonjour
1/6=1/26+1/30+1/36+1/39+1/45+1/52
pour une somme de 228

Merci pour cette enigme

Posté par
Surb
re : Enigmo 300 : Six pour un sixième 02-06-13 à 13:27

perduBonjour,

je propose
\Large{\frac{1}{18}+\frac{1}{24}+\frac{1}{26}+\frac{1}{78}+\frac{1}{104}+\frac{1}{117}}
pour un total de 367 sans être certain que c'est le plus petit.
Si quelqu'un a produit un code efficace pour résoudre ce problème je serai très intéréssé de le voir .

Posté par
masab
re : Enigmo 300 : Six pour un sixième 02-06-13 à 13:44

gagnéBonjour,

On a la décomposition    
1/6 = 1/26 + 1/30 + 1/36 + 1/39 + 1/45 + 1/52

La somme des dénominateurs est égale à 228

Merci pour cette énigme égyptienne !

Posté par
RickyDadj
re : Enigmo 300 : Six pour un sixième 02-06-13 à 15:10

gagnéBonjour Jamo, bonjour tous!
Je propose la décomposition 1/6 = 1/26 + 1/30 + 1/36 + 1/39 + 1/45 + 1/52, avec la somme minimale 26+30+36+39+45+52 = 228.
Merci pour la joute!

Posté par
RickyDadj
re : Enigmo 300 : Six pour un sixième 02-06-13 à 15:16

gagnéPardon. Merci pour l'énigme!
Quoique les énigmes sont autant des joutes que les joutes sont des énigmes...

Posté par
infophile
re : Enigmo 300 : Six pour un sixième 02-06-13 à 16:48

gagnéBonjour

Il n'y a qu'une solution.

Décomposition

\color{red}\frac{1}{6}=\frac{1}{26}+\frac{1}{30}+\frac{1}{36}+\frac{1}{39}+\frac{1}{45}+\frac{1}{52}

Somme

\color{blue}26+30+36+39+45+52=228

Merci pour l'énigme

Posté par
torio
re : Enigmo 300 : Six pour un sixième 02-06-13 à 17:50

gagnéA+
Torio

Enigmo 300 : Six pour un sixième

Posté par
geo3
re : Enigmo 300 : Six pour un sixième 02-06-13 à 18:26

gagnéBonjour
Voici une décomposition 1/26+1/30+1/36+1/39+1/45+1/52 = 1/6
avec pour somme des dénominateurs = 228
Merci et A+

Posté par
fontaine6140
re : Enigmo 300 : Six pour un sixième 02-06-13 à 18:27

gagnéBonjour Jamo,

- la décomposition


\frac{1}{26}+\frac{1}{30}+\frac{1}{36}+\frac{1}{39}+\frac{1}{45}+\frac{1} {52}=\frac{1}{6}


- la somme des 6 dénominateurs 228=26+30+36+39+45+52

Merci pour l'énigmo

Posté par
pierrecarre
re : Enigmo 300 : Six pour un sixième 02-06-13 à 19:21

perduBonsoir,

Ma solution :

la décomposition

1=\dfrac1{15}+\dfrac1{40}+\dfrac1{42}+\dfrac1{55}+\dfrac1{56}+\dfrac1{66}

avec pour somme des dénominateurs

15+40+42+55+56+66=274.

Bien cordialement,

\pi r^2

Posté par
sbarre
re : Enigmo 300 : Six pour un sixième 02-06-13 à 19:39

gagnéBonjour,

1/6 = 1/26 + 1/30 + 1/36 + 1/39 + 1/45 + 1/52
et 26+30+36+39+45+52 = 228

Merci!

Posté par
rogerd
six 02-06-13 à 22:54

gagnéBonjour

Je trouve la décomposition

1/52+1/45+1/39+1/36+1/30+1/26=1/6

La somme des dénominateurs est 228

Posté par
dpi
re : Enigmo 300 : Six pour un sixième 03-06-13 à 08:12

perduBonjour,

Il faut sélectionner les "bons" diviseurs:
1/24+1/30+1/36+1/40+1/45+1/60 pour obtenir 1/6
total des dénominateurs 235

Posté par
GaBuZoMeu
re : Enigmo 300 : Six pour un sixième 03-06-13 à 11:29

gagné\dfrac{1}{6}=\dfrac{1}{26}+\dfrac{1}{30}+\dfrac{1}{36}+\dfrac{1}{39}+\dfrac{1}{45}+\dfrac{1}{52}, total des dénominateurs 228. Merci Sage !

Enigmo 300 : Six pour un sixième

Posté par
gui_tou
re : Enigmo 300 : Six pour un sixième 03-06-13 à 13:46

perduBonjour Jamo,

Je propose :

\dfrac{1}{6}=\dfrac{1}{27}+\dfrac{1}{28}+\dfrac{1}{30}+\dfrac{1}{36}+\dfrac{1}{54}+\dfrac{1}{70}

La somme des dénominateurs est 245

Posté par
rschoon
re : Enigmo 300 : Six pour un sixième 03-06-13 à 19:26

perdu Bonjour à tous.

Je propose :

\frac{1}{6}=\frac{1}{12}+\frac{1}{32}+\frac{1}{48}+\frac{1}{64}+\frac{1}{96}+\frac{1}{192}

Somme des dénominateurs : 444

Merci pour l'énigme

Posté par
plumemeteore
re : Enigmo 300 : Six pour un sixième 03-06-13 à 19:26

perduBonjour Jamo.
Je propose 1/24 + 1/30 + 1/36 + 1/40 + 1/45 + 1/60 = 1/6;
somme des dénominateurs : 235.

Posté par
Chatof
re : Enigmo 300 : Six pour un sixième 04-06-13 à 09:22

gagné\frac{1}{6}=\frac{1}{26}+\frac{1}{30}+\frac{1}{36}+\frac{1}{39}+\frac{1}{45}+\frac{1}{52}
 \\ 
 \\ 26+30+36+39+45+52=228
 \\

26+30+36+39+45+52=228

Bonjour et merci Jamo

Heureusement que j'ai affiné et vérifié  avec la force brute !

Posté par
ksad
re : Enigmo 300 : Six pour un sixième 04-06-13 à 11:54

gagnéBonjour
Je propose la décomposition suivante:

1/6 = 1/52 + 1/45 + 1/39 + 1/36 + 1/30 + 1/26

pour une somme minimale de S = 52 + 45 + 39 + 36 + 30 +26 = 228
Merci pour l'Enigmo !

Posté par
Alexique
re : Enigmo 300 : Six pour un sixième 05-06-13 à 23:14

gagnéBonjour !

Une énigme qui m'a enfin convaincu de me mettre à Maple !
Ci-dessous une procédure (avec des conditions redondantes certes) mais tant qu'on a le résultat dans un temps correct...

On a donc la décomposition \dfrac16=\dfrac1{26}+\dfrac1{30}+\dfrac1{36}+\dfrac1{39}+\dfrac1{45}+\dfrac1{52}
avec 26+30+36+39+45+52=228.

Je serais curieux de savoir s'il y a un algorithme de décomposition d'une fraction unitaire en somme de n fractions unitaires de plus petits dénominateurs possible, ma méthode étant on ne peut plus naïve.

Merci pour l'énigme !

Enigmo 300 : Six pour un sixième

Posté par
Kidam
re : Enigmo 300 : Six pour un sixième 06-06-13 à 11:09

gagnébonjour à tous,

J'espère que j'ai bien trouvé le minimum, car j ai fait toutes mes recherches à la main.

Résultat :

\frac{1}{6} = \frac{1}{26} + \frac{1}{30} + \frac{1}{36} + \frac{1}{39} + \frac{1}{45} + \frac{1}{52}
La somme des dénominateurs est alors de 228.

Kidamicalement

Posté par
eyyad34
Bonjour 09-06-13 à 17:50

perdu La décomposition1/18+1/30+1/45+1/36+1/60+1/90
et la somme des 6 dénominateurs = 279
Merci pour l'énigme

Posté par
frenicle
re : Enigmo 300 : Six pour un sixième 10-06-13 à 13:31

gagnéBonjour jamo,

Je ne trouve pas mieux que 228,

\dfrac{1}{6}=\dfrac{1}{26}+\dfrac{1}{30}+\dfrac{1}{36}+\dfrac{1}{39}+\dfrac{1}{45}+\dfrac{1}{52}
 \\

Merci pour l'enigmo

Posté par
littleguy
re : Enigmo 300 : Six pour un sixième 10-06-13 à 14:01

perduRe-bonjour,

Après avoir "jeté" à la hâte une réponse, je me suis penché sur le problème et ai trouvé plein de réponses moins farfelues.

J'en suis pour l'instant à :  1/26 + 1/30 + 1/36 + 1/39 + 1/45 + 1/52
pour une somme de 228

Il y a sans doute bien mieux. Puisque poisson de toute façon, je me pencherai à nouveau dessus

Posté par
brubru777
re : Enigmo 300 : Six pour un sixième 10-06-13 à 19:20

gagnéBonjour,

On peut dire qu'elle m'a donné du fil à retordre celle-là !

Je trouve {1 \over 6} = {1 \over 26} + {1 \over 30} + {1 \over 36} + {1 \over 39} + {1 \over 45} + {1 \over 52} pour un total de 228.

Merci pour l'énigme.

Posté par
pyth
re : Enigmo 300 : Six pour un sixième 10-06-13 à 20:20

perdu\frac{1}{6}= \frac{1}{36}+\frac{1}{36}+\frac{1}{36}+\frac{1}{36}+\frac{1}{36}+\frac{1}{36}
 \\ somme=216
 \\

Posté par
Glapion Moderateur
re : Enigmo 300 : Six pour un sixième 11-06-13 à 20:03

gagnéBonjour,
mon meilleur score :
\dfrac{1}{6}=\dfrac{1}{26}+\dfrac{1}{30}+\dfrac{1}{36}+\dfrac{1}{39}+\dfrac{1}{45}+\dfrac{1}{52} donnant une somme de 228

Posté par
jugo
re : Enigmo 300 : Six pour un sixième 13-06-13 à 06:57

gagnéBonjour,

Voici ma proposition :

1/6 = 1/26 + 1/30 + 1/36 + 1/39 + 1/45 + 1/52

26 + 30 + 36 + 39 + 45 + 52 = 228

Posté par
totti1000
re : Enigmo 300 : Six pour un sixième 15-06-13 à 18:15

gagnéSalut jamo,

Je propose un minimum de 228 avec la décomposition suivante :

\frac{1}{6}=\frac{1}{26}+\frac{1}{30}+\frac{1}{36}+\frac{1}{39}+\frac{1}{45}+\frac{1}{52}.

Merci.

Posté par
roule
ce fut bon 17-06-13 à 13:57

perdu1/90+1/72+1/60+1/36+1/24+1/18 = 1/6
La somme des 6 dénominateurs est 300.

Posté par
franz
re : Enigmo 300 : Six pour un sixième 19-06-13 à 17:05

gagné\frac 1 6 = \frac 1 {26} + \frac 1 {30} + \frac 1 {36} + \frac 1 {39} + \frac 1 {45} + \frac 1 {52}

La somme des dénominateurs fait 228.

Posté par
dedef
re : Enigmo 300 : Six pour un sixième 19-06-13 à 22:15

perduBonjour

1/24+1/30+1/36+1/42+1/45+1/56
233

Posté par
seb_dji
re : Enigmo 300 : Six pour un sixième 20-06-13 à 12:35

perdu27 54 24 40 35 63
somme= 243

Posté par
gui_tou
re : Enigmo 300 : Six pour un sixième 21-06-13 à 09:36

perduBonjour Jamo,

C'est vendredi, jour du poisson ! J'attends le mien avec impatience

Posté par
derny
Six pour un sixième 23-06-13 à 22:35

perdu1/18 + 1/19 +1/54 + 1/57 + 1/76 + 1/108
somme des dénominateurs : 332
N'ayant pas fait de programme mais quelques rapides tâtonnements il se pourrait fortement que l'on puisse faire mieux !

Posté par
Raphi
re : Enigmo 300 : Six pour un sixième 27-06-13 à 01:38

gagné\frac{1}{6}=\frac{1}{26}+\frac{1}{30}+\frac{1}{36}+\frac{1}{39}+\frac{1}{45}+\frac{1}{52}
Somme : 228

Posté par
jamo Moderateur
re : Enigmo 300 : Six pour un sixième 27-06-13 à 11:36

Clôture de l'énigme

Le minimum était bien de 228, je vous laisse voir la bonne décomposition donnée par plusieurs ci-dessus.

Posté par
gui_tou
re : Enigmo 300 : Six pour un sixième 27-06-13 à 12:25

perduBravo aux bonnes réponses

Posté par
brubru777
re : Enigmo 300 : Six pour un sixième 28-06-13 à 21:50

gagné@Surb

Citation :
Si quelqu'un a produit un code efficace pour résoudre ce problème je serai très intéréssé de le voir


Comme je le disais, j'ai bien galéré pour cette énigme. J'ai essayé plusieurs algorithmes "optimisés" sans succès. Au final, j'ai fait du brut de brut qui m'a donné la solution après de nombreuses heures de laborieux calculs.

Avant-hier, j'ai eu une révélation. J'ai refait tout mon programme qui m'a donné la solution au bout de 30min. Après de nombreuses optimisations acharnées, le temps de calcul est passé à 27s !

Voici le code en question (en Java) :

public class Enigmo300SixPourUnSixième {

    // Le nombre de fractions à trouver
    private final static int NOMBRE = 6;
    // Le total à trouver
    private final static Fraction TOTAL = new Fraction(1, NOMBRE);
    // Le tableau des dénominateurs minimums
    private final static int[] ORIGINAL = new int[NOMBRE];
    
    // Le tableau des dénominateurs du plus petit au plus grand
    private static int[] tab = new int[NOMBRE];
    // Le total des fractions cumulées, en partant de la fin
    // totalFractions[0] contient donc la somme de toutes les fractions
    private static Fraction[] totalFractions = new Fraction[NOMBRE];
    // Le décalage entre les dénominateurs et leur minimum
    // Ils doivent obligatoirement être croissants (ou décroissants si on part
    // de la fin
    private static int[] decalages = new int[NOMBRE];
    // Prends la valeur true si une solution est trouvée
    private static boolean trouve = false;
    
    public static void main(String[] args) {
        Fraction.setSimplificationAuto(true);
        // Remplissage des dénominateurs minimum
        for (int i = 0; i < NOMBRE; i++)
            ORIGINAL[i] = NOMBRE + 1 + i;
        long debut = System.currentTimeMillis();
        long fin;
        // On teste les décalages un par un jusqu'à trouver une solution
        for (int decalageTotal = 1; !trouve; decalageTotal++) {
            resoudre(NOMBRE - 1, decalageTotal);
            // Affichage du décalage et du temps de calcul
            fin = System.currentTimeMillis();
            System.out.println("Décalage = "+decalageTotal+" (trouvé après "+((fin - debut) / 1000.0)+"s)");
            debut = fin;
        }
    }

    private static void afficherSolution() {
        System.out.print("Solution : Total = "+totalNombres()+" : Total fractions : "+totalFractions.toString()+" :");
        for (long i : tab)
            System.out.print(" "+i);
        System.out.println();
    }
    
    private static void afficherSolutionLaTeX() {
        System.out.print("{1 \\over , Total = "+ totalNombres());
    }

    private static void resoudre(int pos, int decalage) {
        int valeur = ORIGINAL[pos];
        if (pos == NOMBRE - 1) {
            for (int i = decalage, reste = 0; (i >= 1) && (reste <= i * pos); i--, reste++) {
                tab[pos] = valeur + i;
                totalFractions[pos] = new Fraction(1, tab[pos]);
                decalages[pos] = i;
                resoudre(pos - 1, reste);
            }
        } else if (pos == 0) {
            if (decalage <= decalages[1]) {
                tab[pos] = valeur + decalage;
                totalFractions[pos] = Fraction.ajouter(totalFractions[pos + 1], new Fraction(1, tab[pos]));
                if (TOTAL.compareTo(totalFractions[0]) == 0) {
                    trouve = true;
                    afficherSolutionLaTeX();
                }
             }
        } else if (decalage == 0) {
            tab[pos] = valeur;
            totalFractions[pos] = Fraction.ajouter(totalFractions[pos + 1], new Fraction(1, tab[pos]));
            if (TOTAL.compareTo(totalFractions[pos]) > 0) {
                decalages[pos] = 0;
                resoudre(pos - 1, decalage);
            }
        } else {
            int imax = Math.min(decalage, decalages[pos + 1]);
            for (int i = imax, reste = decalage - i; (i >= 1) && (reste <= i * pos); i--, reste++) {
                tab[pos] = valeur + i;
                totalFractions[pos] = Fraction.ajouter(totalFractions[pos + 1], new Fraction(1, tab[pos]));
                if (TOTAL.compareTo(totalFractions[pos]) > 0) {
                    decalages[pos] = i;
                    resoudre(pos - 1, reste);
                }
            }
        }
    }

    private static int totalNombres() {
        int total = 0;
        for (int valeur : tab)
            total += valeur;
        return total;
    }
    
}

C'est clairement moins concis que le code de GaBuZoMeu mais il permet de résoudre le problème pour un nombre quelconque. Je me suis amusé à chercher les solution de 2 à 7. Voici les résultats

{1 \over 2} = {1 \over 3} + {1 \over 6}, Total = 9 = 8 + 1
{1 \over 3} = {1 \over 6} + {1 \over 10} + {1 \over 15}, Total = 31 = 27 + 4
{1 \over 4} = {1 \over 10} + {1 \over 15} + {1 \over 21} + {1 \over 28}, Total = 74 = 64 + 10
{1 \over 5} = {1 \over 18} + {1 \over 21} + {1 \over 28} + {1 \over 30} + {1 \over 36}, Total = 133 = 125 + 8
{1 \over 5} = {1 \over 20} + {1 \over 21} + {1 \over 24} + {1 \over 28} + {1 \over 40}, Total = 133 = 125 + 8
{1 \over 6} = {1 \over 26} + {1 \over 30} + {1 \over 36} + {1 \over 39} + {1 \over 45} + {1 \over 52}, Total = 228 = 216 + 12
{1 \over 7} = {1 \over 36} + {1 \over 40} + {1 \over 45} + {1 \over 55} + {1 \over 56} + {1 \over 60} + {1 \over 66}, Total = 358 = 343 + 15

Ce qui est amusant, c'est que la somme minimale est toujours de l'ordre de n3.

J'essaierai demain avec n = 8 mais ça risque d'être long. 27s pour n = 6, 48min pour n = 7 (avant optimisation, c'était plus de 3h) alors pour n = 8... à suivre

Posté par
dpi
re : Enigmo 300 : Six pour un sixième 29-06-13 à 07:34

perduBonjour

J'ai poissonné (de peu),mais je pense que le meilleur
raisonnement est le suivant:

Comme pyth a osé le donner l'idéal est 1/36 6 fois soit 216
Donc l'énigme doit avoir une réponse autour de ce 1/36.
Retenons comme pivot 1/36 et testons les plus proches,en remarquant qu'il faudra
plus de plus grands que de plus petits sois 3 pour 2,il faudra aussi
que la somme des écarts des plus 36 et moins 36 soit égale (ici 0.0974)
Un coup de force brute et bravo à ceux qui ont trouvé 26 30 (36) 39 45 52

Posté par
brubru777
re : Enigmo 300 : Six pour un sixième 29-06-13 à 11:39

gagné@dpi

Cependant, c'est une coïncidence que ça marche pour 6 car 1 / n2 ne figure de aucune autre solution pour n de 2 à 7.

Mais vous m'avez permis de réaliser 2 choses.

1) Je comprends pourquoi les solutions donnent un résultat légèrement supérieur n3 (solution optimale pour n dénominateurs valant n2).

2) Je peux démarrer mon algorithme avec un décalage de n3 - n(3n + 1) / 2 + 1. Ca fera déjà ça de gagné !

Merci

Posté par
brubru777
re : Enigmo 300 : Six pour un sixième 29-06-13 à 12:05

gagnéBon, ben 10s (contre 27s avant) pour n = 6 et 16min (contre 48min avant). Temps de recherche divisé par 3 grâce à dpi. Pour n = 8, ça restera long car ça prend environ 1h30 par itération !

Posté par
dpi
re : Enigmo 300 : Six pour un sixième 29-06-13 à 17:30

perduHeureux de rendre service

Posté par
brubru777
re : Enigmo 300 : Six pour un sixième 30-06-13 à 20:33

gagnéAprès toute une journée de calcul...

{1 \over 8} = {1 \over 50} + {1 \over 55} + {1 \over 60} + {1 \over 63} + {1 \over 66} + {1 \over 72} + {1 \over 75} + {1 \over 84}, Total = 525

J'espère qu'on aura jamais d'énigme Neuf pour un neuvième

Posté par
infophile
re : Enigmo 300 : Six pour un sixième 03-07-13 à 16:55

gagnéBonjour

Après quelques heures de calculs également :

\frac{1}{9}=\frac{1}{105}+\frac{1}{99}+\frac{1}{91}+\frac{1}{88}+\frac{1}{78}+\frac{1}{77}+\frac{1}{72}+\frac{1}{70}+\frac{1}{66}

105+99+91+88+78+77+72+70+66=746=9^3+17

Pas d'énigmes pour moi ce mois-ci, planning bien chargé.

Bonnes vacances et bonne chance aux participants !

Posté par
ArgShX
re : Enigmo 300 : Six pour un sixième 04-07-13 à 14:14

Bonjour,

\dfrac{1}{10}=\dfrac{1}{80}+\dfrac{1}{84}+\dfrac{1}{88}+\dfrac{1}{90}+\dfrac{1}{99}+\dfrac{1}{108}+\dfrac{1}{110}+\dfrac{1}{112}+\dfrac{1}{120}+\dfrac{1}{135}

80+84+88+90+99+108+110+112+120+135=1026=10^3+26

en 58 min 35 sec

Pour 9 je trouve comme infophile en 15 secondes. J'ai fais ça en Java aussi, avec quelques optimisations. Mais au final je gagne pas grand chose : le temps de calcul reste exponentiel (c'est du brut force un peu moins brutal ), et au-delà de 11 ou 12 le temps de calcul redevient trop important.

pour les curieux, voici le code : il est mega moche pour trois raisons : j'ai tout mis dans la même classe pour que vous ayez tout sous les yeux, la récursivité c'est pas tip top et ça m'a conduit à utiliser plein de variables globales statiques (beurk) et surtout je suis pas un adepte du code propre

Citation :

public class Decomposition {
  
  private static final double epsilon = Math.pow(10, -10);
  
  private static int target;
  private static double approx;
  private static int start, width;
  private static int[] solution;
  private static double[] fracs;
  private static boolean stop;
  
  private static int lcm(int a, int b) {
    int aa = Math.max(a, b);
    int bb = Math.min(a, b);
    int r = bb;
    while (r != 0) {
      r = aa % bb;
      aa = bb;
      bb = r;
    }
    return (a * b) / aa;
  }

  public static boolean check(int[] solution) {
    int denom = 1;
    for (int i = 0; i < solution.length; i++) {
      denom = lcm(denom, solution[i]);
    }
    int num = 0;
    for (int i = 0; i < solution.length; i++) {
      num += denom / solution[i];
    }
    return denom % num == 0;
  }
  
  private static void display(int[] t) {
    for (int i = 0; i < t.length; i++) {
      System.out.print(t[i] + "  ");
    }
    System.out.println();
  }
  
  private static void testAll(int n, int k, int width, int[] cnk) {
    if (n == 1) {
      cnk[target - 1] = width - 1;
      double val = 0;
      for (int i = 0; i < cnk.length; i++) {
        val += fracs[cnk[i]];
      }
      if (Math.abs(val - approx) < epsilon) {
        int[] temp = new int[cnk.length];
        for (int i = 0; i < cnk.length; i++) {
          temp[i] = start + cnk[i];
        }
        if (check(temp)) {
          for (int i = 0; i < temp.length; i++) {
            solution[i] = temp[i];
          }
          stop = true;
        }
      }
    } else {
      for (int i = k; i < width - n + 1; i++) {
        cnk[target - n] = i;
        testAll(n - 1, i + 1, width, cnk);
      }
    }
  }
  
  private static void findDecomposition(int n) {
    target = n;
    approx = 1. / n;
    start = n * n - n / 2;
    width = n;
    solution = new int[n];
    stop = false;
    while (start > 0 && !stop) {
      fracs = new double[width];
      for (int i = 0; i < fracs.length; i++) {
        fracs[i] = 1. / (start + i);
      }
      testAll(n, 0, width, new int[n]);
      start -= 1;
      width += 2;
    }
  }

  public static void main(String[] args) {
  
    long startTime, endTime, duration;
  
    startTime = System.nanoTime();
    findDecomposition(6);
    endTime = System.nanoTime();
    duration = endTime - startTime;
  
    System.out.println(duration / Math.pow(10, 9) + " ");
  
    display(solution);
  }

}


Il y a juste à changer l'entrée de findDecomposition dans le main por tester avec différentes valeurs.

Posté par
brubru777
re : Enigmo 300 : Six pour un sixième 07-07-13 à 08:58

gagnéBalèzes les calculs. Chapeau infophile et ArgShX.

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 136:45:21.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !