2

I have been given this challenge:

Examine the series of numbers shown below:
        2 1 4 3 8 5 16 7 32 9 64 ...
2 is the 1st number in the series, 1 is the 2nd number in the series, etc.
Using Bash, create a program that finds the sum of the first 10,000 numbers.
Submit the first 10 digits of the sum as your answer.
(Answer: 2824934064)

The way of going about this I thought is splitting the series into 2, creating a for loop for each sequence and creating a new array from where I want to merge them together.

So the first sequence would be something like

1. Create an array, starting from the number 2, and keep on doubling it until you hit 10000 numbers.

And the second would be

2. Create an array, starting from the number 1, and keep on adding 2 until you hit 10000 numbers.

then a 3rd array where:

3. I join the 2 arrays but it would be something like {value1FromArray1, value1FromArray2, value2FromArray1, value2FromArray2...} Then I would want to have 10000 numbers in the 3rd array which I sum up.

Now, the only thing I'm thinking is...is that my method sounds like it would do the job, but it would be so inefficient. I feel like there is a much more simple method, something do with for loops or while loops. Any suggestions? I have yet to have tried anything.

12
  • 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.
    – jesse_b
    Commented Dec 18, 2019 at 14:13
  • 2
    For steps 1 and 2 you only need 5000 numbers each, not 10000. However this is not the correct approach. The answer to (2+1+4+3+8+...) is equal to (2+4+8+...) + (1+3+5+...). Work these 2 sums out by logic or loops in bc, no bash arrays needed. Hint: the second sum is big but the first is enormous.
    – icarus
    Commented Dec 18, 2019 at 14:29
  • 2
    If the challenger is telling you to use bc then a bash-only solution is not what they are looking for
    – jesse_b
    Commented Dec 18, 2019 at 14:31
  • 1
    @icarus: Yeah my point was that OPs solution is a really long way around to the solution so it should be discarded altogether. No point discussing it.
    – jesse_b
    Commented Dec 18, 2019 at 14:50
  • 2
    @Jesse_b Talking about x-y-problems: analytically evaluating sum_{i=1}^{5000}(2*i) and sum_{i=0}^{4999}(1+2*i) might be a thing if using a bit of Gauß' way of adding consecutive numbers
    – FelixJN
    Commented Dec 18, 2019 at 14:54

6 Answers 6

2

Doesn't give the sum but gets you the answer...

The additive series is tiny compared to the multiplicative one and can be safely ignored. Forget it.

As has been said above, the multiplication only ever concerns itself with the first 10 digits. The multiplier is 2 so there will never be more than a 1 digit increase in the length of the result and we just need to keep the result within bash comfort zone for math, while keeping it long enough to retain accuracy for the carry.

s=2; for ((i=1; i<=5000; i++)); do s=$((2*s)); s=${s:0:15}; done; echo ${s:0:10}

2824934064

And just because @rastafile fried my brain with treatment of the carry in the geometric series, here is another version which I find more intuitive, though it's pure plagiarism I admit

sum=2; carry=0; rgstr=
for ((i=1;i<=5000;i++)); do
  #calculate from right to left over the string in sum
  for (( j=${#sum}-1; j>=0; j-- )); do
    #get the digit
    x=${sum:$j:1}
    #double the digit and add the current carry
    x=$((x * 2 + carry))
    #get the new carry
    carry=$((${#x}-1))
    #compose the intermediate string
    #carry naturally indexes to the rightmost digit in x
    rgstr=${x:$carry:1}$rgstr
  done
  #deal with any remaining carry before going round again
  if [ $carry -eq 1 ]; then rgstr=$carry$rgstr; carry=0; fi
  #load the sum from the register and then zero it 
  sum=$rgstr
  rgstr=
  (( $i % 100 == 0 )) && echo "$i iterations, sum is ${#sum} digits long"
done
echo "First ten digits of sum are ${sum:0:10}"
10
  • This really improves my carry handling: I do only the digit-doubling first, and then have to juggle around with carry old and new. I guess I had fried my own brain by the time it somehow worked. Thank you for sorting this out.
    – user373503
    Commented Dec 21, 2019 at 14:26
  • Was surprised to get an accepted answer off of the back of @rastafile work, specially as I didn't even add in the other series. Would be good to if you at least upvote them in recognition. Credit where credit is due.
    – bu5hman
    Commented Dec 21, 2019 at 14:34
  • I did upvote, true, but not accept your answer. it is NOT my question. I even had upvoted the Q, but I really do not see where else I should give credit. The keep-only-15 digits method is nice, but why 15 and not 11 digits? And then this whole story with the two-series-in-one, and the challenge, and the 10 first digits. And no reaction from OP after initial disussions. Concerning 2^5001: I want to expand it to use an array of large numbers, to speed it up - let the CPU do 99% percent of the math; the first carry would be ~10 billion.
    – user373503
    Commented Dec 21, 2019 at 22:19
  • My comment was to OP re recognising your good work, wasn't intended as any criticism of you my friend.
    – bu5hman
    Commented Dec 22, 2019 at 16:05
  • In that case...I have only one thing to add: merry christmas! (also to OP, and everybody else ;)
    – user373503
    Commented Dec 22, 2019 at 16:51
1

One line command to execute in shell (/bin/sh or /bin/bash):

A=2;B=1;S=0;i=1;while [ $i -le 60 ];do S=$(($S+$A+$B));A=$(($A*2));B=$(($B+2));i=$(($i+1));done;while [ $i -le 5000 ];do S=$(($S+$A));A=$(($A*2));A=${A:0:14};S=${S:0:14};i=$(($i+1));done;echo "${S:0:10}"

Result:

2824934064

Explanation:

# Initial variables
# A for array 1 member,
# B for array 2 member,
# S for sum we are looking for
# i to count number of iterations from 1 to 5000
A=2;B=1;S=0;i=1;
# For the first 60 arrays members, shell still can handle numbers,
# also second array influences the end result,
# so lets count result for 60 members separately
while [ $i -le 60 ] ; do
    S=$(($S+$A+$B));
    A=$(($A*2));
    B=$(($B+2));
    i=$(($i+1));
done; 
# now result is about 19 symbols long,
# so, array 2 members which are 3 digit numbers
# do not influence the end result at all anymore,
# so we forget about array 2.
# also we restrict length of sum and members of array 1
# to less symbols.. I just take first 14 symbols each time
while [ $i -le 5000 ]; do 
    S=$(($S+$A));
    A=$(($A*2));
    A=${A:0:14};
    S=${S:0:14};
    i=$(($i+1));
done;
# print first 10 symbols of result
echo "${S:0:10}"

Actually the result corresponds to what was expected ;-)

1
  • 1
    +1 for the oneliner. Just for others, inside $(()) adding $ before the variable is not necessary. S=$(($S+$A+$B)) is equivalent to S=$((S+A+B)) same for [ $i -le 60 ] which will be (( i <= 60 ))
    – Rakib Fiha
    Commented Dec 18, 2019 at 16:46
1
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.

0

Bash only can not handle such large numbers.

To show that you can try:

echo "$((2**3))" # result is 8
echo "$((2**5000))" # result is 0

The largest multiplier is 63 but that result in a large negative number:

echo "$((2**63))" # result is -9223372036854775808

The largest multiplier for a positive result is 62:

echo "${{2**62))" # result is 4611686018427387904

Using the suggested bc you can do the following:

bc can also be used with loops, according to the manual man bc search for loop.

This way you can write a loop like:

for (i=1;i<=5000;i++)
{
  double *=2
  odd += 2
}

If you initialize double and odd with values 1 like:

double=2
odd=1

and iterate 5000 to get a total of 10,000 numbers you can sum those two using

total=double+odd

This 'program' can be used in bash to assign it's result into a variable like:

read total < <(echo "double=2;odd=1;for (i=1;i<=5000;i++){double*=2;odd+=2}; total=double+odd;total"|bc -l)

To print only the first 10 digits you can use the bash substring syntax:

echo ${total:0:10}

Then your answer will be:

2824934064

As the result of doubling the initial value 2 5000 times, adding the value of odd won't change the first 10 digits. So in fact the actual result can be simplified to:

read total< <(echo "2^5001"|bc -l)
echo ${total:0:10} 
3
  • 1
    Shouldn't you initialize double with 2 since that's the first number in the sequence?
    – AdminBee
    Commented Dec 18, 2019 at 16:21
  • @AdminBee I think what he is trying to show is just something to get me to think about. I don't think it's the actual code I am supposed to use, but more of a guide to get me to start thinking and to obviously replace any values where needed. Commented Dec 18, 2019 at 16:46
  • @AdminBee, you're right, I updated the answer
    – Lambert
    Commented Dec 18, 2019 at 18:31
0

If I understand correctly the challenge, the two series to be totalized are:

k  2^k  2*k-1 
1    2    1
2    4    3
3    8    5
4   16    7
...

Up to a value k of 5000 (5000 items of series 1 and 5000 items of series 2).

The size of numbers that 2^k will produce for k near the end are quite big. The shell arithmetic could not work with such big numbers, but bc could.

A short script in bc could perform the whole calculation:

$ bc <<<"n=5000;"'while(k++<n){sum+=(2^k+k*2-1)};sum'

28249340642788520736704193340322946673377923503690822336273761717142\
36339685415025116178252633423052746712064168627321655284076761399586\
76671942371453279846862103555703730798023755999290263414138746996425\
26264750510622243074568807190180107190972146683690681115113347360313\
11748109293992809981016993989447158018112351427532364564328684263630\
41983113354252997303564408348123661878478353722682766588036480451677\
38545119229401028848656215055125899067818762639793347126721265938204\
76849082516717773137462679625744819600176761473364436085288658217880\
61578040438881156396976534679536477744559804314840614495141020847691\
73774519347178361163745559287150603703617328271202570260509345364601\
85004366560365038146804908997263665312759757243970220927259709238991\
74562238279814456008771885761907917633109135250592173833771549657868\
89988272483317735065388066512220732911396524441366894843962216374480\
98590069639827534807596519975828237596054351677709971502305989434869\
38482234140460796206757230465587420581985312889685791023660711466304\
04160831584018008362390376091341103093669889236546348465537197855521\
52414190517566375329767366979300309499957282395308828667138560246882\
23531470672787115758429874008695136417331917435528118587185775028585\
68711409417832975296623323138377240762599511138034378433946751044893\
80649501575956618026431598802546744213887545668798445605481215964695\
73480869786916240396682202067625013440093219782321400568004201960905\
92807957740867060523867519572410438456074296226432829437302833818183\
4408818750

It takes a couple of seconds. A faster way is to avoid the recalculation of an exponential on each loop and use a var e*=2 on each loop which raises to the next power of 2 by just a multiplication.

$ bc <<<"n=5000;"'e=2;o=1;while(k++<n){sum+=e+o;e*=2;o+=2}; sum'

Which yields the same result and takes only 0.1 seconds.

It could even be improved. It is known that the sum of k terms of each series is:

sum{1}{k}( 2^j ) = 2^(k+1)-2 sum of powers
sum{1}{k}( 2*j-1 ) = k^2 sum of odd numbers

So, the result, without any loop (very fast, 10 miliseconds) is this math calculation:

echo "k=5000; 2^(k+1)-2+k^2" | bc

And, to print only the first 10 digits:

$ echo "k=5000; sum=2^(k+1)-2+k^2;sum/10^(length(sum)-10)" | bc
2824934064
0
#!/bin/bash

# Examine the series of numbers shown below:
#         2 1 4 3 8 5 16 7 32 9 64 ...
# 2 is the 1st number in the series, 1 is the 2nd number in the series, etc.
# Using Bash, create a program that finds the sum of the first 10,000 numbers.
# Submit the first 10 digits of the sum as your answer.
# (Answer: 2824934064)

# ok, the series is actually TWO series alternating
# A: 2, 4, 8, 16, 32... -> n(x)=n(x-1)*2  -> geometric series
# B: 1, 3, 5, 7, 9...   -> n(x)=n(x-1)+2 -> arithmetic series

# 10,000 numbers means an "n" of 5000 for each series.

# A: calculate sum of a geometric series
# https://www.varsitytutors.com/hotmath/hotmath_help/topics/geometric-series
# common ratio here is 2
# sum=( a1 * ( 1 - 2^n) ) / ( 1 - 2 )

# B: calculate the sum of an arithmetic progression:
# https://www.wikihow.com/Find-the-Sum-of-an-Arithmetic-Sequence
# sum= n * ( a1 + an ) / 2 # a1 is the first number in the series,
# an is the last -- (n-1)*2 in this specific case.

declare -i n
n=${1:-5000}

if [[ $n -eq 0 ]]; then
  echo '[ERROR] I need an integer number.'
  exit 1
fi

sum=$( echo "\
  ( ( 2 * ( 1 - 2 ^ $n )) / ( 1 -2 ) ) \
  + \
  ( $n * ( 1 + ( ( $n - 1) * 2) ) / 2 )" \
  | bc \
  )

echo ${sum:0:10}

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .