doubt--NEED HELP

for the following link

why is the answer for n>22 is same as for n=22.

Ya it will be the same because you have to print it modulo 8388608.

So, for all the number n>=22 answer will be same as your modulo-1.

For an input n, the answer is 2^{n-1}\times(n^2 - n + 2) - 1.
The output to be printed is the answer modulo 8388608, and 8388608 = 2^{23}.

For all n>=24, it is clear that 2^{n-1}\times(n^2 - n + 2) will be divisible by 2^{23}, so the answer will be (-1)\%2^{23}=2^{23}-1.

For n=23, it turns out that (n^2-n+2) = 508 which is divisible by 4.
So 2^{22}\times508 = 2^{24}\times127 is also divisible by 2^{23}.

Similarly for n=22, (n^2-n+2) = 464 = 2^4\times29
and 2^{21}\times464=2^{25}\times29, once again divisible by 2^{23}.

For n=21 however, (n^2-n+2) = 422 = 2\times211 and 2^{20}\times2\times211 is not divisible by 2^{23}.
For all n<21 this property holds.

So for all n>=22, the answer will be in the form of 2^{23}\times k - 1, and the answer modulo 2^{23} will be 2^{23}-1. Hope this is clear!

2 Likes

I am posting this here because I couldn’t find a way to comment on meooow’s answer. My question is that how did you arrive on the formula 2^{n-1}\times(n^2-n+2)-1 .

1 Like

@suyash01 I got the formula by calculating the fourth term (which is 111) and plugging the sequence into OEIS :wink:
This was the result, only the indices are 0-based here so I had to adjust that. Whenever you find an integer sequence, more often than not OEIS will have it. However since you asked, I worked out the formula on paper as well as a mathematical exercise :slight_smile:
alt text

2 Likes

Many thanks for your answer, greatly appreciate it. However I don’t have enough rep to vote up your ans, sorry.

thanks a lot

No problem. Have an upvote so you can comment and stuff!