Как создать 2 массива последовательностей чисел и периодически соединять их вместе? (Баш)
Эта строка помогла мне :https://www.linuxquestions.org/questions/linux-software-2/viewing-bios-settings-from-within-linux-290492/
По сути, запуск dmidecode от имени пользователя root сгенерировал много информации о моей системе.
Только Bash не может обрабатывать такие большие числа.
Чтобы показать, что вы можете попробовать:
echo "$((2**3))" # result is 8
echo "$((2**5000))" # result is 0
Наибольший множитель равен 63, но это приводит к большому отрицательному числу:
echo "$((2**63))" # result is -9223372036854775808
Наибольший множитель для положительного результата равен 62:
echo "${{2**62))" # result is 4611686018427387904
С помощью предложенного bcможно сделать следующее:
bcтакже можно использовать с циклами, в соответствии с ручным поиском man bcдля loop.
Таким образом, вы можете написать такой цикл, как:
for (i=1;i<=5000;i++)
{
double *=2
odd += 2
}
Если вы инициализируете двойное и нечетное значениями 1, например:
double=2
odd=1
и повторите 5000, чтобы получить в общей сложности 10 000 чисел, которые вы можете суммировать, используя
total=double+odd
Эту «программу» можно использовать в bash для присвоения результата переменной, например:
read total < <(echo "double=2;odd=1;for (i=1;i<=5000;i++){double*=2;odd+=2}; total=double+odd;total"|bc -l)
Чтобы напечатать только первые 10 цифр, вы можете использовать синтаксис подстроки bash:
echo ${total:0:10}
Тогда ваш ответ будет:
2824934064
В результате удвоения начального значения 2 5000 раз добавление значения oddне изменит первые 10 цифр. Таким образом, фактический результат можно упростить до:
read total< <(echo "2^5001"|bc -l)
echo ${total:0:10}
Однострочная команда для выполнения в оболочке (/bin/sh или /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}"
Результат:
2824934064
Пояснение:
# 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}"
На самом деле результат соответствует ожидаемому;-)
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
Первые 10 цифр такие же, как в OP.
Из этого числа 2^5001нужно вычесть 2, а затем прибавить другой ряд, 1+3+5+7... (см. ниже)
Насколько я понимаю, задача состоит в том, чтобы получить точный результат. Десять первых цифр — это только быстрая проверка, а не решение.
Вот сценарий bash. Это занимает около 60 секунд. Я немного сжал его, чтобы он подходил.
# 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"
Я опустил все "$" (, где это возможно, следуя комментарию rakib ). См. ответ бушмена для более прямого обращения с переноской.
Другая серия — это:
]# for ((z=1; z < 10000; z+=2)) do s=$((s + z)); done
]# echo $s
25000000
]# echo $(( (1+9999) * 2500 ))
25000000
последние 9 цифр 2^5001равны
]# echo ${n:${#n}-9}
383818752
Это можно добавить, без ухищрений:
]# echo $((383818752 + 25000000))
408818752
Я думаю, что есть еще минус 2, который нужно запомнить, из-за того, как я суммировал серию 2+4+8+16....
Итак, у нас есть echo ${#n}1506 -цифровое число, начинающееся с echo ${n:0:10}2824934064... и заканчивающееся на...408818750. Остальные 1487 цифр :см. выше.
Конечно, полным решением было бы создание (двух )рядов и добавление элементов один за другим по мере их поступления, пока не будет добавлено 10 000 из них. Но для этого нужен более общий строковый -калькулятор, и тогда элементы геометрического ряда сами становятся слишком большими.
Идея в том, что числа очень большие, но необходимая операция очень проста :только умножение на 2. И сложения можно упростить:
2+4+8+16 = 32 - 2
(или1+2+4+8 = 15 = "F" hex = "1111" bin = 2^4 - 1)
Итак, одна из ваших сумм равна 2^5001 - 2. По крайней мере, bcдает те же 10 первых цифр -, что все число легко умещается на экране.
Внутри bc, с некоторыми перестановками,вы можете получить это напрямую:
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
Сумма нечетных чисел (1+3+5+7... ), вплоть до n-го числа, представляет собой просто n квадрат, как указано в другом вопросе. Это было хорошо известно Галилею (Википедия не упоминает об этом явно ). То, что (n+1)^2есть n^2 + 2n + 1, иллюстрируется увеличением квадрата :, вам понадобятся две «полосы» плюс «угол» :
...1
...1
...1
222X
«Фокус» с суммированием всех чисел от 1 до 100 я услышал от своего учителя математики 40 лет назад, с красивой историей об Эйлере (или Гауссе ), которым в школе сказали вычислить это -учитель хотел тихий час. Но через 5 минут будущий гений покончил с собой, превратившись 1+2+3+4+5+6...+100в:
1 + 100 +
2 + 99 +
3 + 98 +
...
9 + 92 +
10 + 91 +
...
50 + 51
Сумма равна 50 * 101. Трудная часть состоит в том, чтобы убедиться, что «спаривание» правильное.
Итак, я использовал 5000/2 * (1+9999)или 10^4/4 * 10^4, и это то же самое, что и 5000^2. Генерал:(n/2)^2 = n^2 / 4 = n * n/4. Я не знаю, логично это или сбивает с толку.
Проблема остается неясной. Но зацикливание на bcкажется мне слишком простым. Я перевернул его и суммировал серию напрямую (обман)-все же мне потребовалось 5000 итераций из-за гигантских чисел, и нет bc.
Если я правильно понимаю задание, суммируются две серии:
k 2^k 2*k-1
1 2 1
2 4 3
3 8 5
4 16 7
...
До значения k, равного 5000 (5000 изделий серии 1 и 5000 изделий серии 2 ).
Размер чисел, которые 2^kвыдает для k ближе к концу, довольно велик. Арифметика оболочки не могла работать с такими большими числами, но bcмогла.
Короткий скрипт на bc мог бы выполнить все вычисления:
$ 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
Это занимает пару секунд. Более быстрый способ - избежать пересчета экспоненты в каждом цикле и использовать переменную e*=2в каждом цикле, которая возводится в следующую степень 2 простым умножением.
$ bc <<<"n=5000;"'e=2;o=1;while(k++<n){sum+=e+o;e*=2;o+=2}; sum'
Это дает тот же результат и занимает всего 0,1 секунды.
Его можно было бы даже улучшить. Известно, что сумма k членов каждого ряда равна:
сумма{1}{k} (2^j )= 2^ (k+1 )-2 сумма степеней
sum{1}{k} (2 *j -1 )= k^2 сумма нечетных чисел
Итак, результат без цикла (очень быстрый, 10 миллисекунд )это математический расчет:
echo "k=5000; 2^(k+1)-2+k^2" | bc
И, чтобы напечатать только первые 10 цифр:
$ echo "k=5000; sum=2^(k+1)-2+k^2;sum/10^(length(sum)-10)" | bc
2824934064
Сумму не дает, но дает ответ...
Аддитивный ряд крошечный по сравнению с мультипликативным, и им можно смело пренебречь. Забудь это.
Как было сказано выше, умножение касается только первых 10 цифр. Множитель равен 2, поэтому длина результата никогда не увеличится более чем на 1 цифру, и нам просто нужно удерживать результат в комфортной зоне bashдля математики, сохраняя при этом его длину достаточной, чтобы сохранить точность переноса.
s=2; for ((i=1; i<=5000; i++)); do s=$((2*s)); s=${s:0:15}; done; echo ${s:0:10}
2824934064
И только потому, что @rastafile поджарил мой мозг обработкой переноса в геометрическом ряду, вот еще одна версия, которую я нахожу более интуитивной, хотя это чистый плагиат, который я признаю
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}"
#!/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}