To memorize slokas in ancient time people performed various recitation styles for complete and perfect memorizations, one of which is Ghanapatha. In essence it is just a permutation with repetition of words in different orders.
python3 ghanapatha.py
- In this problem we will first store the words of the string in an array.
- We can then see than ghanapatha is the sequence
1221123321123
repeated each time with+1
to each term, i.e.1221...
$\to$ 2332...
. - So we loop through this sequence and print the corresponding word each time by an offset of
-1,0,1,2,...
(-1
for 0-based indexing) to the numbers in the sequence until the maximum index is contained in the string. - This means that
$3+\text{offset}<\text{length}(\text {string})$
dhiyah. yah. na pracodayāt
Ghanapatha for given text is:
dhiyah. yah. yah. dhiyah. dhiyah. yah. na na yah. dhiyah. dhiyah. yah. na ;
yah. na na yah. yah. na pracodayāt pracodayāt na yah. yah. na pracodayāt ;
An algorithm by pingala to write binary numbers with given number of digits.
python3 pingala_binary_sequence.py
- This problem is based on recursive algorithm where the function returns a list
[0, 1]
if$n=1$ . - Otherwise it first recurses to get list for
$n=n-1$ and then for every binary string in that list, it first appends0
to it and then finally1
to all of them. - Finally it returns the constructed binary sequence (In
$L\to R$ manner).
5
Binary sequence of n bits written in L-R manner is
00000
10000
01000
11000
00100
10100
01100
11100
00010
10010
01010
11010
00110
10110
01110
11110
00001
10001
01001
11001
00101
10101
01101
11101
00011
10011
01011
11011
00111
10111
01111
11111
The famous O(log n)
power of 2 algorithm.
python3 pingala_2_pow_n.py
- In this problem if
$n=0$ we return1
, else we recurse in the following manner:- If
$2\mid n$ , we returnpow(n/2)*pow(n/2)
else - If
$2\not\mid n$ , we returnpow(n-1)*2
- If
123
2^n using pingala's algorithm is: 10633823966279326983230456482242756608
An algorithm to solve the linear diophantine equation ax+c=by
.
python kuttaka.py
- We first check if
gcd(a, b)
dividesc
.If gcd is>1
Then we divide by common gcd. We makeA, B, C
as positive values ofa, b, c
- We then create a list for quotients na dmake dividend and divisor as
A
andB
. - We find remainders until we get 1 and make valli.
- Finally we multiply the penultimate term with the factor above and add the next term. We expunge the last term and repeat this process till we have only 2 values in the column.
- Then we deal with special cases
a < 0
,b < 0
andc < 0
. - Then we subtract
a
andc
times the minimum dividend when dividingy
andx
respectively.
ax + c = by
Enter a: 60
Enter c: 3
Enter b: 13
60 * 11 + 3 = 663 = 663 = 13 * 51
Solution is (11, 51)
Solves the quadratic Pell-like equation Pq^2+s=r^2
through Chakravala method.
python chakravala.py
- We first nearest square to
P
, i.e.$\left(\text{round}(\sqrt P)\right)^2$ ,r
as$P\cdot1^2+s=r^2\implies r=\sqrt{s+P}$ and$q=1$ . - Then while we get
$s=\pm1,\pm2\pm4$ , we solve$qx+r=sy$ (ignoring sign) using previously made kuttaka. Let us get$(x,y)$ as the solution. - Then we will have
$(x+ks,y+kq)$ as another solution, so we need to minimize$|P-X^2|=|P-(x+ks)^2|$ which is concave, so minima will be near root, i.e.$\frac{\sqrt{P}-x}s$ , so we check both integers near to this value and find required$(X, Y) = (x+ks,y+kq)$ . - Then we take
$s=-\frac{X^2-P}s$ (neglecting sign) and$q=Y, r=\sqrt{Pq^2+s}$ . - Then we do bhavana, where we use the two rules:
- Solution of
$Pq^2+c=r^2$ is$(\alpha, \beta)$ then solution of$Pq^2+c/k^2=r^2$ is$(\alpha/k,\beta/k)$ . - Solution of
$Pq^2+k=r^2$ is$(\alpha, \beta)$ then solutions of$Pq^2+k^2=r^2$ is$(2\alpha\beta, P\alpha^2+\beta^2)$ , or if we have another solution$(\alpha_1,\beta_1)$ then$(\alpha\beta_1+\alpha_1\beta,P\alpha\alpha_1+\beta\beta_1)$ - We do the following transformations:
-1 -> 1
,4 -> 1
,-4 -> -1 -> 1
,2 -> 4 -> 1
,-2 -> 4 -> 1
.
- Solution of
Pq^2 + s = r^2
Enter P: 61
Enter s: 1
61 * 226153980 ^ 2 + 1 = 3119882982860264401 = 3119882982860264401 = 1766319049 ^ 2
Solution is (226153980, 1766319049)