Para N = 2 no es posible
N = 3 1 3 2
N = 4 1 3 2 4
N = 5 1 3 2 4 5
N = 6 1 3 2 4 5 6
N = 7 1 3 2 4 5 6 7
N = 8 8 1 3 2 4 5 6 7
N = 9 9 8 1 3 2 4 5 6 7
N = 10 10 9 8 1 3 2 4 5 6 7
N = 11 11 10 9 8 1 3 2 4 5 6 7
N = 12 12 11 10 9 8 1 3 2 4 5 6 7
¿Se podrá siempre ordenar los números de 1 a N para que el producto menos uno de dos números vecinos sea primo?
Esta entrada forma parte del carnaval de matemáticas edición 4.123 que en esta ocasión organiza el blog Eulerianos
Si lo quieres compartir o guardar
Entradas
Parece que hay montonazillones y montonazillones de soluciones. Para encontrarlas he construido el grafo de números que pueden ser vecinos y he buscado caminos hamiltonianos por fuerza bruta; la única "astucia" ha sido no dejar vértices aislados. Para N = 13 hay 1921 soluciones, y para N = 14 hay 22822. El problema se empieza a hacer difícil cuando N = 30. Para N impar, he usado el truco de buscar soluciones que empiecen por 1 3 2 y a partir de entonces alternen pares e impares (no puede haber dos impares juntos a menos que sean 1 y 3, porque entonces a*b-1 tiene que ser par y no puede ser primo). Es sorprendente, pero con este truco resulta fácil encontrar soluciones hasta N = 175 o así. La solución para N = 185 necesitó unas 2^32 llamadas recursivas. ¿Puede alguien confirmar que esto son soluciones? Me resulta raro.
ResponderEliminar// 13: 13 8 10 11 12 9 2 7 6 5 4 3 1
// 14: 14 13 8 10 11 12 9 2 7 6 5 4 3 1
// 15: 1 3 2 7 14 13 8 9 6 15 10 11 4 5 12
// 20: 1 3 2 4 5 6 17 16 15 10 9 8 19 20 7 12 11 18 13 14
// 25: 1 3 2 7 6 5 4 11 10 23 16 17 22 9 8 13 14 21 12 19 20 25 18 15 24
// 30: 1 3 2 4 5 6 7 12 9 8 13 14 21 20 19 30 15 10 11 24 25 18 29 28 23 16 17 22 26 27
// 35: 1 3 2 7 6 5 4 11 10 9 8 13 14 21 12 15 16 23 28 29 18 25 20 33 26 27 22 35 24 31 32 19 30 17 34
// 55: 1 3 2 7 6 5 4 11 10 9 8 13 14 21 12 15 16 17 22 27 24 25 18 29 28 23 36 19 20 31 30 35 40 33 26 43 48 39 38 49 32 45 52 41 42 37 44 51 34 47 46 53 54 55 50
// 99: 1 3 2 7 6 5 4 11 10 9 8 13 14 21 12 15 16 17 22 27 24 25 18 29 28 23 36 19 20 31 30 35 40 33 26 39 38 45 32 49 48 43 60 41 42 37 44 51 34 47 46 53 54 55 50 61 72 65 58 69 56 57 52 59 70 63 66 67 62 75 64 95 76 77 94 93 68 81 92 97 74 91 84 83 78 73 80 87 86 99 82 89 96 79 98 85 90 71 88
//149: 1 3 2 7 6 5 4 11 10 9 8 13 14 21 12 15 16 17 22 27 24 25 18 29 28 23 36 19 20 31 30 35 40 33 26 39 38 45 32 49 48 43 60 41 42 37 44 51 34 47 46 53 54 55 50 61 72 65 58 69 56 57 52 59 70 63 66 67 62 75 64 95 76 77 94 71 82 89 90 73 78 81 68 85 86 79 96 97 74 91 84 83 108 99 80 87 100 113 124 137 144 101 88 105 98 103 104 115 114 93 106 117 102 109 122 127 116 133 110 121 92 111 128 139 138 119 112 125 130 131 132 129 140 141 142 107 136 147 134 123 120 143 148 135 146 145 126 149 118
//185: 1 3 2 7 6 5 4 11 10 9 8 13 14 21 12 15 16 17 22 27 24 25 18 29 28 23 36 19 20 31 30 35 40 33 26 39 38 45 32 49 48 43 60 41 42 37 44 51 34 47 46 53 54 55 50 61 72 65 58 69 56 57 52 59 70 63 66 67 62 75 64 95 76 77 94 71 82 89 90 73 78 81 68 85 86 79 96 97 74 91 84 83 108 99 80 87 100 101 88 105 98 103 104 115 114 93 106 117 102 109 122 127 116 133 110 121 92 111 124 107 136 119 112 125 126 123 120 143 148 131 130 141 128 139 138 165 118 149 142 147 132 129 140 135 134 145 152 177 170 169 150 179 168 151 158 159 160 155 154 113 156 173 180 153 144 171 174 185 184 167 172 161 178 183 146 157 176 163 164 181 182 175 162 137 166