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
$\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}$

| improve this answer | |
$\endgroup$
  • $\begingroup$ I don't see how you are taking the minimum with $1/2^{n-1}$ for each $m$. $\endgroup$ – The Substitute Jul 13 '17 at 17:30
  • $\begingroup$ @TheSubstitute Min is called within MapThread as many times as the Length of ms $\endgroup$ – Coolwater Jul 13 '17 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 '17 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.