userNetwork.php

<?php
/**
 * @param integer $p Posição do usuário
 * @param integer $t Total de elementos
 * @param integer $q Razão da rede
 * @return integer
 */
function userNetwork($p, $t, $q = 2)
{
    $sigma = function($n) use ($q) { return (pow($q, $n) - 1) / ($q - 1); };

    if ($t >= $p) {
        //calculando a altura do nível do usuário
        for ($nP = 1; ($snP = $sigma($nP)) < $p; ++$nP);

        //calculando a altura da árvore
        for ($n = $nP; ($sn = $sigma($n)) < $t; ++$n);

        //calculando o tamanho da rede do usuário
        $userNetwork = ((pow($q, $n - $nP + 1) - 1) / ($q - 1));

        //A árvore é completa?
        if ($t < $sn) {
            //Qual a posição do usuário, no nível dele?
            $up = ($snP - $sigma($nP - 1)) - ($snP - $p);

            //Quantos amigos ele deverá ter no último nível?
            $apn = pow($q, $n - $nP);

            //Quantos amigos existem no último nível dessa árvore?
            $ull = $t - ($sn - pow($q, $n - 1));

            //A rede do usuário é completa?
            if ($up * $apn > $ull) {
                //Corrige o total de amigos na rede do usuário
                $ull = $ull - (($up - 1) * $apn);

                $userNetwork -= $apn - ($ull < 0?0: $ull);
            }
        }

        return $userNetwork;
    }

    return 0;
}