La course de Spiderman

Même les super-héros ont des tocs arithmétiques...

Il y avait un problème dans ce défi (non détecté car apparu suite à un changement de version de Python, je crois).
Le problème est maintenant réglé, semble-t-il...

Tout le monde sait que Peter Parker, alias Spiderman, est aussi un étudiant brillant. En revanche, ses manies au sujet des nombres sont moins connues. Ainsi, certains jours, Spidey s'impose des règles quant aux numéros des buildings auxquels il va accrocher sa toile pour remonter une rue.

La première règle est qu'il doit alterner un fil de chaque côté de la rue. Autrement dit, après avoir lancé un fil sur un immeuble avec un numéro pair, il lancera un fil sur un immeuble avec un numéro impair, et inversement...

Mais ce n'est pas tout. Certains jours, il n'accepte de lancer un fil sur un building impair que si le numéro de celui-ci est un nombre premier.

Un jour, il remarque que pour un nombre pair donné supérieur ou égal à 4, il est possible d'écrire ce nombre comme la somme de deux nombres premiers. Par exemple, 8 s'écrit 5 + 3 (5 et 3 sont tous les deux premiers). Pour 14, il y a deux solutions : 7 + 7, ou bien 11 + 3. Pour 24, il y a trois solutions : 13 + 11, 17 + 7, et 19 + 5. De cette constatation, est née chez Spidey une affection immodérée pour les nombres pairs pour lesquels le problème précédent a une quantité impaire de solutions (Peter Parker n'est pas quelqu'un de simple...). Ainsi, les premiers nombres pairs qu'il affectionne sont :

  • 4 (2 + 2) (rappelons que 2 est un nombre premier, le seul qui soit pair)
  • 6 (3 + 3)
  • 8 (5 + 3)
  • 12 (7 + 5)
  • 22 (11 + 11, 17 + 5, 19 + 3)
  • 24 (13 + 11, 17 + 7, 19 + 5)
  • ....

En revanche, 10, par exemple, n'est pas dans sa liste, car il peut s'écrire comme la somme de deux nombres premiers de 2 manières différentes : 5 + 5 et 7 + 3.

Aujourd'hui, Spidey a décidé qu'en plus d'alterner un numéro pair et un numéro impair, qu'en plus de choisir uniquement des numéros impairs qui soient premiers, il choisirait uniquement des numéros pairs qui sont dans la liste de ses favoris (4, 6, 8, 12, 22, 24... mais pas 10, 14, 16...).

Sachant qu'il lance son premier fil sur le building numéro 3 et que son dernier fil doit lui permettre d'atteindre exactement le building dont le numéro est donné en entrée du problème ; sachant de plus qu'il lance toujours un fil vers le building le plus proche qu'il s'autorise à utiliser (en fonction de son numéro) ; combien de fils devra-t-il utiliser ? Et quel sera son saut le plus long ? Pour aider Spidey, relevez ce défi et donnez comme réponse les deux nombres attendus.

Exemple : Partant du building 3, si le building à atteindre avait le numéro 31, alors Spidey lancerait ses fils sur les immeubles :

3, 4, 5, 6, 7, 8, 11, 12, 13, 22, 23, 24, 29, 30, 31

Il aurait donc besoin de 15 fils, et le saut le plus long aurait pour longueur 9, en passant de l'immeuble 13 à l'immeuble 22. La réponse au défi serait alors : 15, 9

Ce problème est tiré de c0d1ng UP 2016

Type de retour

deux nombres entiers

Entrée du problème

709

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup16 arithmétique