How to find the maximum value of n that satisfies the sum of a sequence of numbers?

Question

Given the sequence a[n], the sum of the first n terms in the sequence is s[n],

where n is a positive integer.

When n is at [2^(k-1), 2^k), then a[n_]=2^k, and k is a positive integer,

find the maximum value of the positive integer n that holds s[n]<2022

a[n_] = If[{2^(k - 1) <= n < 2^k, k \[Element] PositiveIntegers}, 2^k]

I tried it myself, but there was a problem with the general formula

Answer 1

Clear[a, s]
a[n_Integer] := Module[
  {k},
  k = Floor[Log[2, n] + 1];
  2^k]
s[n_Integer] := Sum[a[i], {i, 1, n}]

NestWhile[# + 1 &, 1, s[#] < 2022 &] - 1
(* 51 *) 

s[51]
(* 1962 *)
s[52]
(* 2026 *)

---

EDIT:

a[i]s are repeatedly computed with the above implementation with Sum and NestWhile, e.g., in testing s[4]<2022 after testing s[3]<2022, all the a[i]s except a[4] are recomputed.

Note that s[n] = s[n-1] + a[n], so we may just:

First[NestWhile[{#[[1]] + 1, #[[2]] + a[#[[1]] + 1]} &, {1, 
    a[1]}, #[[2]] < 2022 &]] - 1

(* 51 *) 

Another way, we may use the memoization, such as this and that by szhorvat.

Answer 2

If you want to avoid iterating it can be done formulaically. We use a function to compute the sum for powers of 2 and another to give the n that gets to such a power.

sum1[k_] = Sum[2^n*2^(n - 1), {n, k}];
sum2[k_] = Sum[2^(n - 1), {n, k}];

We also need a function to invert the first one above and extract the Floor.

lowExponent[n_] := Floor[First[NSolveValues[sum1[k] == n && k > 1, k]]]

Now we can use these and do a quick quotient to see how far we have to go at the next level.

maxUnder[n_] := With[{lowE = lowExponent[n]},
  sum2[lowE] + Floor[(n - sum1[lowE])/2^(lowE + 1)]]

Example:

maxUnder[2022]

(* Out[331]= 51 *)

I apologize for the uninspired function names and the even less inspired explanation. Maybe it's just not my day for clarity.

On the plus side, this method is pretty fast.

maxUnder[2022^202] // Timing

(* Out[361]= {0.003634, \
8848412971663091221718486019366725826876038928718791960496214510185100\
2756313339789362784310738600294437488431058648509122782268195260731096\
2698748759207703006494701238381383269788249231560021717717656442703134\
6136171077852358900869531539535081576202445462527581584040000708152338\
085124485774977647714843738024701074430022309498144970} *)

(Better to be fast than pretty, as they say in track.)