(Resolvido) Sequencia exponencial de 2 - Validar soma?

[LucasConstantino]

Olá!

Então, pessoal. A coisa parece simples em si, mas eu andei pensando um pouco em soluções. Encontrei algumas mas todas muito trabalhosas e extensas. Eis o problema:

Se eu defino uma progressão geométrica de 2 iniciando em 1 eu crio o conjunto/progressão:

P = ( 1, 2, 4, 8, 16, 32, 64... )

Não preciso explicar muito o que eu preciso, pois todos já devem ter feito uma prova de somatória na vida.

Dado um número, por exemplo "53", como faço para descobrir quais termos da progressão foram somados para resultar tal número? Nesse caso, teriamos;

1 + 4 + 16 + 32 = 53

Então os termos somados seriam: 1º, 3º, 5º, 6º.

Como faço para chegar a essa conclusão utilizando PHP?

____

Minha primeira idéia foi verificar gradualmente o primeiro número menor em relação ao número dado. Digamos; se o valor final fosse 53, então ele verificaria, dentro da array que contém a prograssão geométrica, qual o primeiro menor ou igual número com relação a este.

( 1, 2, 4, 8, 16, 32, 64... )

53 >= 32 -> 32 é o primeiro menor ou igual número antes de 53

Então faria a diferença " 53 - 32 = 21 " e salvaria o termo utilizado numa array " termos_utilizados = Array( 6 ) "

Logo faria novamente o processo, encontrando a diferença: " 21 - 16 = 5 " e salvaria novamente o termo utilizado na array " termos_utilizados = Array( 6, 5 ) "

Outra vez: " 5 - 4 = 1 " / " termos_utilizados = Array( 6, 5, 3)

Última vez: " 1 - 1 = 0 " / " termos_utilizados = Array( 6, 5, 3, 1 )

Agora como eu faria esse código do PHP? Alguma idéia? E alguém imagina outra solução? Os vestibulares utilizam essa formula e isso é feito automaticamente dentro do sistema deles, para verificar quais as respostas do candidato escolhei numa questão somatória.

Obrigado!

Lucas.

[LucasConstantino]

Bom, eu consegui uma solução como a que eu mesmo falei acima. Eis o código:

function somatorio( $soma )
    {
        $result = array();
        
        while( $soma > 0 )
        {
            $count = 1;
            while( $soma > $count )
            {
                $count = $count * 2;
            }
            if( $count > $soma )
            {
                $count /= 2;
            }
            $result[] = $count;
            $soma -= $count;
        }
        
        return( $result );
    }

Exemplo:

somatorio( "42" ) será = array( 32, 8, 2 )

RESOLVIDO

Editado Setembro 12, 2009 por LucasConstantino