How to create 2 number sequence arrays and join them together intermittently? (Bash)

Question

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.

Answer 1

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}"

Answer 2

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 ;-)

Answer 3

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.

Answer 4

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} 

Answer 5

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

Answer 6

#!/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}