Re: Fila de Números (verao mais completa)

["Eduardo Casagrande Stabel" <duda@xxxxxxxxxx>]

Caro Rubens,

o maior numero de n algarismos e' 10^n - 1, e o menor numero de n algarismos
e' 10^(n-1), incluindo esses dois numeros temos [(10^n - 1) - 10^(n-1)] + 1
= 10^n - 10^(n-1) = (10 - 1)*10^(n-1) = 9*10^(n-1) numeros com n algarismos.
Chamemos K(n) a funccao que denota o numero de algarismos que contem todos
os numeros de n algarismos, o que resulta K(n) = n*9*10^(n-1). Se queremos
descobrir a posiccao de um determinado numero M (com 10^(N-1) <= M < 10^n,
ou seja, M tem N algarismos), na sua fila de numeros, e sabemos que ha (M -
10^(N-1)) numeros, menores do que M, com N algarismos. Temos que

 P(M) = K(1) + ... + K(N-1) + N*(M - 10^(N-1)) + 1        'acrescento 1, por
que nao existe 0-esima posiccao

A soma K(1) + ... + K(N-1) resulta em N*10^(N-1) - (10^N - 1)/9 (mais
detalhes de como calcular essa formula, veja * ), donde temos:

 P(M) = N*10^(N-1) - (10^N - 1)/9 + N*(M - 10^(N-1)) + 1

Em particular N = floor( log(M)/log(10) ) + 1, onde floor é a função menor
inteiro.

Vemos que:

P(1) = 1
P(10) = 10
P(100) = 190
P(1000) = 2890

Portanto, N=3, e:

P(M) deve ser o menor ou igual a 1264, e P(M+1) deve ser maior.

P(M) = - 110 + 3M  (lembrando que M tem 3 algarismos)
Se -110 + 3M = 1264, teriamos M = 458, logo P(458) = 1264, e temos o
algarismo 4 na 1264a. posiccao.



* A soma dos K's e' similar a soma S = q^0 + 2*q^1 + 3*q^2 + ... n*q^(n-1),
um modo de achar uma formula para essa soma eh reescreve-la da seguinte
forma (chame T = q^0 + ... + q^(n-1) ):

S = q^0 + q^1 + ... + q^(n-1)
              + q^1 + ... + q^(n-1)
                            ...
                                + q^(n-1)
   =    T
      + T - q^0
      + T - q^0 - q^1
      + ...
      + T - q^0 - q^1 - ... - q^(n-2)
  = n*T - [ (q^1 - 1)/(q - 1) + (q^2 - 1)/(q-1) + ... + (q^(n-1) - 1)/(q -
1) ]
  = n*T - 1/(q - 1) * [ T - q^0 - (n-1) ]
  = n*T - (T - n)/(q - 1)

Ja que temos a formula de T = (q^n - 1)/(q - 1), com alguma manipulaccao
chegamos a uma formula para S.

Muito obrigado!
Eduardo Casagrande Stabel.


De: Rubens
Para: obm-l@mat.puc-rio.br

Caros Amigos,
Me ajudem neste problema:
" Escrevendo a seqüência de números Naturais, sem separar os algarismos
1234567891011121314151617181920212223242526... Encontar o algarismo que
ocupa o 1264º lugar.

Desde já obrigado.

Rubens