1
$\begingroup$

Given a positive integer $n$, let $p$ denote the largest prime $p$ less than $2^n$.

That is, $p$ equals

Max[Table[Prime[i], {i, 1, PrimePi[2^n]}]]

I want to form a sum by adding some terms for each $1\le m<2^n$.

Given the prime factorization $m=2^{a_2}\cdots p^{a_p}$, consider $k/m$ for primes $k$ with $a_k>0$.

For each $k$, form the sum $k/m+k/(2m)+k/(2^2m)+\cdots$ such that in reduced form the highest power of 2 in the denominator is $2^{n-2}$.

Specifically, if $k=2,$ take the sum

Sum[2/(2^i *m), {i,0,n-a_2-1}]

and if $k\not =2$, then take the sum

Sum[k/(2^i *m), {i,0, n-a_2-2}]

Then I want to add all of these new sums together (over the $k$'s with $a_k>0)$, divide the result by 2, and then take the minimum with $1/2^{n-1}$. This is the total contribution I want to assign to $m$, call it $Y_m$. What would be a code for $\sum_{1\le m<2^n}Y_m$?

Illustrative Example

If $n=5$ and $m=12=2^2*3$. Since $a_2,a_3>0$, I have $\color\red{k=2},\color\green{k=3}.$

For $k=2,$ I have $2/12=2/(2^23), $ so in the sum I include $\color\red{2/(2^23)+2/(2^33)+2/(2^43)}$

For $k=3,$ I have $3/12=3/(2^23)$, so in the sum I include $\color\green{3/2^2+3/2^33}$

Therefore, the contribution I assign to $m=12$ is $$Y_{12}=\min\bigg((1/2)[\color\red{(2/(2^23)+2/(2^33)+1/(2^43))}+\color\green{(3/(2^23)+3/(2^33))}],\frac{1}{2^{5-1}}\bigg).$$

$\endgroup$

1 Answer 1

1
$\begingroup$
Table[ms = Range[2, 2^n - 1];
  Total[MapThread[With[{Q = FirstCase[#, {2, q_} -> q, 0]},
    Min[#3, Total[Outer[Divide, #[[All, 1]]/#2, 2^Range[0, n - 2 - Q]],
     {1, 2}]/2 + If[OddQ[#2], 0, 2^(Q - n + 1)/#2]]] &,
       {FactorInteger[ms], ms, ConstantArray[2^(1 - n), 2^n - 2]}]], {n, 9}]

$\left\{0,1,\frac{3}{2},\frac{7}{4},\frac{15}{8},\frac{31}{16},\frac{63}{32},\frac{127}{64},\frac{255}{128}\right\}$

FindSequenceFunction[%, n] // FullSimplify

$2-2^{2-n}$

$\endgroup$
3
  • $\begingroup$ I don't see how you are taking the minimum with $1/2^{n-1}$ for each $m$. $\endgroup$ Jul 13, 2017 at 17:30
  • $\begingroup$ @TheSubstitute Min is called within MapThread as many times as the Length of ms $\endgroup$
    – Coolwater
    Jul 13, 2017 at 17:35
  • 1
    $\begingroup$ 2n-2 is how many values of $m$ to be summed over, excluding $m=1$ because 1 = "no factors" -> min(0, 2^(1-n)) -> 0. For other p it will be p^n - 2 $\endgroup$
    – Coolwater
    Jul 17, 2017 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.