GLAT – 17

17. Considerar una función la cual, para un entero n, devuelve el número unos requeridos para escribir todos los numero entre 0 y n. Por ejemplo f(13)=6. Note que f(1)=1 Cual es de los siguientes el más grande n el cual cumple que f(n)=n?

Este es con el que me atasqué. Intuía como encontrar la respuesta y por donde andaría, pero no llegue a ella en su momento porque las primeras cuentas básicas las había echado mal, y despues no me las replantee. Hoy en cuanto he revisado lo que habia hecho me he dado cuenta del error.

Bueno, vamos al grano:

Me he basado en las diferencias (D=n-f(n)). Vamos a comprobar los numeros maximos de n cifras, así como el siguiente numero empieza por uno, por lo tanto no suman, y se pasa por números que restan, si es pequeño solo habrá que ver cuantos se necesitan restar. Además es una buena forma de ver como crecen las funciones implicadas:
Max(N(1))=9; f(9)=1; D(1)=8
Max(N(2))=99; f(99)=20; D(2)=79
Max(N(3))=999; f(999)=300; D(3)=699
Se ve claramente como evolucionan, asi que llegando al numero en que la cifra mas significativa de la diferencia sea 0 estaremos más cerca del número que buscamos. Por si quedan dudas me he hecho un programa. Lo he hecho en fortran con el compilador Plato3 (o el que integra el entorno). Si hubiese usado el hugs de haskell, habría podido obtener cuantos valores quisiera, pero este ya lo tengo bastante olvidado (falta de uso) y me tuve que mirar la sintaxis del otro para explicarselo a la chavala, así que he usado lo que tenía más fresco. Además es mas que suficiente:

program diferencias integer::i,diferencia,max,f,error=0    character(len=15),parameter::archivo='diferencias.txt'    i=1 f=0    open(unit=10,file=archivo,status='UNKNOWN',action='WRITE',iostat=error,access='SEQUENTIAL',position='ASIS')    if (error/=0) Then   write (*,*) 'Ha ocurrido un error al intentar abrir el archivo: ',archivo else   !Habra un overflow si llegamos a 10      do while(i<10)    max = (10**i) -1       f = (f*10)+(10**(i-1))       diferencia=max - f    write(10,*,iostat=error) i,' digitos: ', diferencia, '; max=',max,'; f=',f        if (error/=0) Then       write (*,*) 'Ha ocurrido un error (',error,') al intentar escribir el archivo: ',archivo          exit        end if        i = i +1      end do      close(10)    end ifend program diferencias

No hacía falta lo de sacarlo a un archivo, pero bueno, por enredar.
El resultado es:

1 digitos:            8; max=           9; f=           12 digitos:           79; max=          99; f=          203 digitos:          699; max=         999; f=         3004 digitos:         5999; max=        9999; f=        40005 digitos:        49999; max=       99999; f=       500006 digitos:       399999; max=      999999; f=      6000007 digitos:      2999999; max=     9999999; f=     70000008 digitos:     19999999; max=    99999999; f=    800000009 digitos:     99999999; max=   999999999; f=   900000000

Por suerte, antes del overflow por la capacidad de los enteros, hemos conseguido reducir la cifra mas significativa de la diferencia hasta 0 ;).
Además se ve claramente que debido al crecimiento de f(n) en la siguiente iteración tendría una cifra más que max,con lo que la siguiente linea sería:

10 digitos: -1; max= 9999999999; f= 10000000000

Con lo que f(9999999998) = 9999999998.

Ahora bien, me acabo de dar cuenta de que me he acelerado, y puede que esa no sea la respuesta, ya que se pide el menor n, y f(n) vale 9999999998 dese 9999999991. Aunque es posible (muy posible ya que n crece linealmente y f(n) a saltos) que en el momento en que se cruzan las funciones f(n) y n no se de la igualdad f(n)=n, pero sin embargo sin comprobarlo de algun modo, no puedo decir que esta sea la respuesta….

Vaya mierda!!, jeje.

CORRECCIÓN: Al releer todo me he dado cuenta de que he metido la para dos veces: no se pide el menor, y f(9999999998) = 10000000000. Me he liado, pero bueno, está cerca la cosa, otro dia lo acabo.

Autor: Javi López

Arquitecto/desarrollador, creativo, buscador de nuevas soluciones y modelos de negocio, crítico constructivo y ex muchas cosas