![[+]](../images/find.png "show/hide quicksearch"){kind=small}
Supplementary module: Discrete Mathematics for fun
Sources:
The Great Courses: “An Introduction to Number Theory“ (INT)
All the methods are module functions (via module_function).
From the Great Courses: “An Introduction to Number Theory”, Lecture 2: conjecture.
Any natural number n will eventually result in sequence 1, 4, 2, 1, 4, 2, 1, … (hailstone sequences) based on the following algorithm:
If n is even
replace n with n / 2
If n is odd
replace n with 3n + 1
It has been proven to numbers up to around 3e18.
Returns true.
Tsr::DM.dm_3np1(30) 30 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 (19 terms, max = 160) => true
# File rtensor_sup.rb, line 653
653: def dm_3np1 ( n, cnt = 1, max = 0 ) # => true
654: print(' ', n)
655: max = n if max < n
656: raise(ArgumentError, 'n cannot be less than one.') if n < 1
657: if n == 1
658: puts(" (#{cnt} terms, max = #{max})")
659: return true
660: end
661:
662: if n % 2 == 0
663: DM.dm_3np1(n / 2, cnt + 1, max)
664: elsif n % 2 == 1
665: DM.dm_3np1(3 * n + 1, cnt + 1, max)
666: else
667: raise(ArgumentError, 'n has to be integer.')
668: end
669: end
From the Great Courses: “An Introduction to Number Theory”, Lecture 7: theorem.
Generates the prime number by the method next.
p = Tsr::DM.dm_prime p.next => 2 p.next => 3 p.next => 5
# File rtensor_sup.rb, line 804
804: def dm_prime # => Prime class
805: require 'prime'
806: Prime::EratosthenesGenerator.new
807: end
From the Great Courses: “An Introduction to Number Theory”, Lecture 7: theorem.
Generates the prime factorization by returning an array of the prime numbers and their powers.
Tsr::DM.dm_prime_division(12) => [[2, 2], [3, 1]]
# File rtensor_sup.rb, line 816
816: def dm_prime_division ( n ) # => array
817: require 'prime'
818: Prime.prime_division(n)
819: end
From the Great Courses: “An Introduction to Number Theory”, Lecture 2: theorem.
Any natural number n is the prefix of some power of 2.
Returns the power of 2.
Tsr::DM.power_of_2(30) 30 is 2 to the power of 78 (302231454903657293676544) => 78
# File rtensor_sup.rb, line 681
681: def power_of_2 ( n ) # => int
682: ns = n.to_s
683: len = ns.size
684:
685: cnt = 0
686: num = 1
687: while (num.to_s.size != len)
688: cnt += 1
689: num *= 2
690: end
691:
692: while (num.to_s)[0, len] != ns
693: cnt += 1
694: puts(" power = #{cnt}") if cnt % 10000 == 0
695: num *= 2
696: end
697:
698: print(' ', ns, ' is 2 to the power of ', cnt, ' (', num, ")\n")
699: cnt
700: end
Corollary: Any natural number n is the infix of some power of 2.
Returns the power of 2 and the offset.
Tsr::DM.power_of_2_infix(30) 30 is 2 to the power of 22 with offset 4 (4194304) => [22, 4]
For example, a particular phone number is [38552, 7151].
# File rtensor_sup.rb, line 711
711: def power_of_2_infix ( n ) # => array
712: ns = n.to_s
713: len = ns.size
714:
715: cnt = 0
716: num = 1
717: while (num.to_s.size != len)
718: cnt += 1
719: num *= 2
720: end
721:
722: found = false
723: while ! found
724:
725: nums = num.to_s
726: offset = 0
727: (0..nums.size - len).each do |start|
728: if (nums)[start, len] == ns
729: offset = start
730: found = true
731: break
732: end
733: end
734:
735: if found
736: break
737: end
738:
739: cnt += 1
740: puts(" power = #{cnt}") if cnt % 10000 == 0
741: num *= 2
742: end
743:
744: print(' ', ns, ' is 2 to the power of ', cnt, ' with offset ', offset, ' (', num, ")\n")
745: [cnt, offset]
746: end
Returns the inverse of power_of_2_infix by specifying the power of two, offset, and length.
Tsr::DM.power_of_2_inverse(22, 4, 2) => "30"
# File rtensor_sup.rb, line 753
753: def power_of_2_inverse ( pow, offset = 0, len = 1) # => str
754: ((2**pow).to_s)[offset, len]
755: end
From the Great Courses: “An Introduction to Number Theory”, Lecture 7: theorem.
Generates the prime numbers by returning an array of the prime numbers within the specified limits.
Tsr::DM.prime_set(100, 50) => [53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
# File rtensor_sup.rb, line 828
828: def prime_set ( final = 100, init = 2 ) # => array
829: require 'prime'
830: set = []
831: Prime.each(final) {|p| set.push(p) if p >= init}
832: set
833: end
From the Great Courses: “An Introduction to Number Theory”, Lecture 5: theorem.
Any natural number n can be written as a sum of distinct Fibonacci numbers.
Returns an array of fibbonaci numbers.
Tsr::DM.sum_of_fibonacci(100) 100 = 89 + 8 + 3 => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
# File rtensor_sup.rb, line 767
767: def sum_of_fibonacci ( n ) # => array
768: fibo = []
769: fibo[0] = 0
770: fibo[1] = 1
771: cnt = 1
772: # puts(" F[#{cnt}] = #{fibo[cnt]}")
773: while fibo.last < n
774: fibo[cnt + 1] = fibo[cnt] + fibo[cnt - 1]
775: cnt += 1
776: # puts(" F[#{cnt}] = #{fibo[cnt]}")
777: end
778: rem = n
779: print(rem, ' = ')
780: while rem != 0
781: if fibo[cnt] <= rem
782: rem -= fibo[cnt]
783: print(fibo[cnt])
784: print(' + ') if rem > 0
785: end
786: cnt -= 1
787: end
788: puts
789: return fibo
790: end
Disabled; run with --debug to generate this.
Generated with the Darkfish Rdoc Generator 1.1.6.