1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024
11 2048
12 4096
...
32 4294967296
...
48 281474976710656
...
64 18446744073709551616
...
1000 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
2000 114813069527425452423283320117768198402231770208869520047764273682576626139237031385665948631650626991844596463898746277344711896086305533142593135616665318539129989145312280000688779148240044871428926990063486244781615463646388363947317026040466353970904996558162398808944629605623311649536164221970332681344168908984458505602379484807914058900934776500429002716706625830522008132236281291761267883317206598995396418127021779858404042159853183251540889433902091920554957783589672039160081957216630582755380425583726015528348786419432054508915275783882625175435528800822842770817965453762184851149029376
3000 1230231922161117176931558813276752514640713895736833715766118029160058800614672948775360067838593459582429649254051804908512884180898236823585082482065348331234959350355845017413023320111360666922624728239756880416434478315693675013413090757208690376793296658810662941824493488451726505303712916005346747908623702673480919353936813105736620402352744776903840477883651100322409301983488363802930540482487909763484098253940728685132044408863734754271212592471778643949486688511721051561970432780747454823776808464180697103083861812184348565522740195796682622205511845512080552010310050255801589349645928001133745474220715013683413907542779063759833876101354235184245096670042160720629411581502371248008430447184842098610320580417992206662247328722122088513643683907670360209162653670641130936997002170500675501374723998766005827579300723253474890612250135171889174899079911291512399773872178519018229989376
...
END: 282493406427885207367041933403229466733779235036908223362737617171423633968541502511617825263342305274671206416862732165528407676139958676671942371453279846862103555703730798023755999290263414138746996425262647505106222430745688071901801071909721466836906811151133473603131174810929399280998101699398944715801811235142753236456432868426363041983113354252997303564408348123661878478353722682766588036480451677385451192294010288486562150551258990678187626397933471267212659382047684908251671777313746267962574481960017676147336443608528865821788061578040438881156396976534679536477744559804314840614495141020847691737745193471783611637455592871506037036173282712025702605093453646018500436656036503814680490899726366531275975724397022092725970923899174562238279814456008771885761907917633109135250592173833771549657868899882724833177350653880665122207329113965244413668948439622163744809859006963982753480759651997582823759605435167770997150230598943486938482234140460796206757230465587420581985312889685791023660711466304041608315840180083623903760913411030936698892365463484655371978555215241419051756637532976736697930030949995728239530882866713856024688223531470672787115758429874008695136417331917435528118587185775028585687114094178329752966233231383772407625995111380343784339467510448938064950157595661802643159880254674421388754566879844560548121596469573480869786916240396682202067625013440093219782321400568004201960905928079577408670605238675195724104384560742962264328294373028338181834383818752
The first 10 digits are the same as in OP.
From this number 2^5001
one has to subtract 2, and then add the other series, the 1+3+5+7... (see below)
As I understand the challenge is to get the precise result. The ten first digits are only the quick check, not the solution.
Here is the bash script. It takes about 60 seconds. I squeezed it a bit so it fits.
# reads $n from right to left and doubles each digit, with carry
doubn () {
carry=0; newn=''
for (( pos = ${#n} - 1; pos >= 0; pos-- ))
do
d=${n:pos:1}
dd=$(( 2 * d ))
if (( ${#dd} > 1 ))
# only take second digit, but keep new carry
then newd=${dd:1:1}; newcar=1
else newd=$dd; newcar=0
fi
# add (old) carry and save the new; $newd is max 8!
(( carry )) && (( newd++ ))
carry=$newcar
# build the new (doubled) string
newn="$newd$newn"
done
# add last carry, avoid leading zero
(( carry )) && n="$carry$newn" || n=$newn
}
n='1'
for (( cnt=1; cnt <= 5001; cnt++ ))
do
doubn
# print selected steps
(( cnt <= 64 || cnt % 1000 == 0 )) && echo "$cnt $n"
done
echo "END: $n"
I left out all the "$" (where possible, following rakib's comment). See bushman's answer for a more direct carry handling.
The other series is:
]# for ((z=1; z < 10000; z+=2)) do s=$((s + z)); done
]# echo $s
25000000
]# echo $(( (1+9999) * 2500 ))
25000000
The last 9 digits of 2^5001
are
]# echo ${n:${#n}-9}
383818752
This can be added, without tricks:
]# echo $((383818752 + 25000000))
408818752
I think there is also that minus 2 to remember, because of the way I summed up the 2+4+8+16... series.
So we have a echo ${#n}
1506-digit number starting with echo ${n:0:10}
2824934064... and ending with ...408818750. The other 1487 digits: see above.
Of course, the full solution would be to really generate the (two) series and add the items one by one, as they come, until you have added 10'000 of them. But that needs a more general string-calculator, and then the items of the geometric series get too large themselves.
The idea is that the numbers are very large, but the operation needed is very simple: only multiplying by 2. And the additions can be simplified:
2+4+8+16 = 32 - 2
(or 1+2+4+8 = 15 = "F" hex = "1111" bin = 2^4 - 1
)
So one of your sums is 2^5001 - 2
. At least bc
gives the same 10 first digits - the whole number fits easily on a screen.
Inside bc
, with some rearrangements, you can have that directly:
2^5001 - 2 + 10^8/4
28249340642788520736704193340322946673377923503690822336273761717142\
36339685415025116178252633423052746712064168627321655284076761399586\
76671942371453279846862103555703730798023755999290263414138746996425\
26264750510622243074568807190180107190972146683690681115113347360313\
11748109293992809981016993989447158018112351427532364564328684263630\
41983113354252997303564408348123661878478353722682766588036480451677\
38545119229401028848656215055125899067818762639793347126721265938204\
76849082516717773137462679625744819600176761473364436085288658217880\
61578040438881156396976534679536477744559804314840614495141020847691\
73774519347178361163745559287150603703617328271202570260509345364601\
85004366560365038146804908997263665312759757243970220927259709238991\
74562238279814456008771885761907917633109135250592173833771549657868\
89988272483317735065388066512220732911396524441366894843962216374480\
98590069639827534807596519975828237596054351677709971502305989434869\
38482234140460796206757230465587420581985312889685791023660711466304\
04160831584018008362390376091341103093669889236546348465537197855521\
52414190517566375329767366979300309499957282395308828667138560246882\
23531470672787115758429874008695136417331917435528118587185775028585\
68711409417832975296623323138377240762599511138034378433946751044893\
80649501575956618026431598802546744213887545668798445605481215964695\
73480869786916240396682202067625013440093219782321400568004201960905\
92807957740867060523867519572410438456074296226432829437302833818183\
4408818750
The sum of uneven numbers (1+3+5+7...), up to the nth number, is simply n square, as pointed out in another question. This was well known to Galileo (wikipedia does not mention it explicitly). That (n+1)^2
is n^2 + 2n + 1
is illustrated by enlarging a square: you neeed two "bars" plus the "corner":
...1
...1
...1
222X
The "trick" to sum all numbers from 1 to 100 I heard from my math teacher, 40 years ago, with a nice story about Euler (or Gauss), who was told at school to calulate it - the teacher wanted a quiet hour. But after 5 minutes the future genius was finished, transforming 1+2+3+4+5+6...+100
into:
1 + 100 +
2 + 99 +
3 + 98 +
...
9 + 92 +
10 + 91 +
...
50 + 51
The sum is 50 * 101
. The hard part is to make sure the "pairing" is correct.
So I used 5000/2 * (1+9999)
, or 10^4/4 * 10^4
, and this is the same as 5000^2
. General: (n/2)^2 = n^2 / 4 = n * n/4
. I don't know if this is logical or confusing.
The challenge remains unclear. But a loop into bc
seems to me too simple. I turned it around and summed the series directly (cheating) - still I needed 5000 iterations because of the giant numbers, and no bc
.
bc <<<$(cut -d' ' -f 1-10000 file.txt | tr ' ' '+') | cut -c10
. I don't know where you came up with your idea but it's definitely not a good way to do this.bc
then a bash-only solution is not what they are looking forsum_{i=1}^{5000}(2*i)
andsum_{i=0}^{4999}(1+2*i)
might be a thing if using a bit of Gauß' way of adding consecutive numbers