A propósito de Ormiston

Un algoritmo de comparación de cifras

En la entrada anterior señalábamos, un poco de pasada, que los pares de Ormiston están formados por dos números primos consecutivos que presentan las mismas cifras, aunque en distinto orden. El primer par está formado por 1913 y 1931. Todo esto está estudiado y puedes consultar estas secuencias en OEIS:

Pares de Ormiston: https://oeis.org/A072274

Tripletes: https://oeis.org/A075093

Conjuntos de cuatro primos consecutivos: https://oeis.org/A161160

Pares que sólo se diferencian en las dos últimas cifras: https://oeis.org/A162765

No vamos a seguir la teoría de estos números, no muy interesante, sino las posibles búsquedas de los mismos con hoja de cálculo. Como de hecho ya están encontrados, nuestro interés se dirigirá al procedimiento de búsqueda.

Si se piensa un poco en la misma se pueden distinguir tres fases:

• Identificar los números primos
• Para cada uno de ellos encontrar el siguiente primo
• Comparar las cifras de ambos para ver si son las mismas.

Como los dos primeros presentan menos novedad, los abordaremos al final. Comenzaremos con la detección de igualdad en el conjunto de cifras.

1) Las mismas cifras en distinto orden

Aquí tenemos el problema que deseábamos resolver hoy:

¿Qué algoritmo podemos usar para saber si dos números enteros tienen las mismas cifras, con el mismo número de repeticiones, y posiblemente en distinto orden?

El problema está en las repeticiones, porque saber si un número contiene a las cifras del otro es fácil, pero el que el número de repeticiones coincida, ya es más difícil de averiguar (para la máquina). Por ejemplo, 51613 y 51631 forman un par de Ormiston y el algoritmo ha de detectar que el 1 aparece dos veces en ambos números. Si no, no serían de Ormiston. ¿Cómo hacerlo?

Se nos ha ocurrido ir tachando una cifra cada vez que comprobemos que también está en el otro par. Leemos la primera cifra del primer número y la buscamos en el otro, y si la encontramos se tacha. Así seguimos hasta que exista una discrepancia o el agotamiento de las cifras. En el caso del ejemplo:

51613   1613   613   13   3
51631   1631   631   31   3

Expresado en pseudocódigo:

Se leen los números m y n
Se convierten en texto (para que el manejo de las cifras sea más rápido)
* Mientras no se agoten las cifras de m se hace lo siguiente:
    Buscamos una coincidencia de la primera cifra de m con cualquiera de n
    Si se da la coincidencia, se tacha esa cifra tanto en m como en n
    Si no hay coincidencia se para el bucle y se avisa
* Fin del mientras
Se lee si hay coincidencia plena o hubo un fallo

En atención a quienes no tienen interés por el código en Basic, lo situamos al final.

2) Identificar un número como primo

Aprovechamos este tema para introducir una mejora en el algoritmo de averiguar si un número es primo o no, sugerida por nuestro amigo Goyo Lekuona. En este blog, por simplicidad, buscábamos los divisores de un número entre los pares y los impares, pero una vez descartado el 2, se puede seguir con los impares. Con ello el tiempo se reduce casi a la mitad. Gracias, Goyo.

El nuevo código puede ser (hay alguna otra variante posible):

Public Function esprimo(a) As Boolean
Dim n, r
Dim es As Boolean
'Devuelve true si es primo. No analiza el que sea entero, por lo que en un decimal puede dar respuesta ilógica
If a = 1 Then es = False ‘El 1 no es primo
If a = 2 Then es = True ‘El 2 sí lo es
If a > 2 Then
If a / 2 = Int(a / 2) Then
es = False  ‘Si el número es par lo descartamos
Else
    n = 3: es = True: r = Sqr(a)
    While n <= r And es = True
    If a / n = Int(a / n) Then es = False ‘Probamos con todo los impares hasta la raíz cuadrada
    n = n + 2
    Wend
End If
End If
esprimo = es
End Function

Una pequeña cuestión: ¿funciona para N=3? ¿Por qué?

3) Buscar el próximo primo

Es muy simple y no necesita explicación:

Function primprox(a) As Long
Dim p, prim As Long
Dim sale As Boolean
'Encuentra el menor número primo mayor o igual al dado
p = a + 1: sale = False: prim = 0
While Not sale
If esprimo(p) Then prim = p: sale = True
p = p + 1
Wend
primprox = prim
End Function

Con estas herramientas hemos reproducido fácilmente los primeros pares de Ormiston, y te invitamos a intentarlo

 Para probar las funciones y aunque bastaba con una inspección visual, hemos pedido a la hoja un listado de pares de Ormiston en los que no haya cifras repetidas. Aquí tienes los primeros:

Anexo

Código de la función cifras_identicas

Public Function cifras_identicas(m, n) As Boolean
Dim i
Dim vale, esta As Boolean
Dim nn$, mm$, c$


nn$ = haztexto(n) ‘Convierte los números en textos
mm$ = haztexto(m)
vale = True
While Len(mm$) > 0 And vale
c$ = Mid$(mm$, 1, 1) ‘toma la primera cifra
esta = False
i = 1
  While i <= Len(nn$) And Not esta
    If c$ = Mid$(nn$, i, 1) Then
    esta = True
    mm$ = borracar(mm$, 1) ‘si ha coincidencia, borra la cifra
    nn$ = borracar(nn$, i)
    End If
    i = i + 1
Wend
If Not esta Then vale = False ‘si no hay coincidencia, sale del bucle con el valor “false”
Wend
cifras_identicas = vale
End Function