Wikipedia:School and university projects/Discrete and numerical mathematics/Learning plan/Sandbox

Minihackathons

Important: This section comes from Epistemowikia, although, to prevent confusion, the corresponding page has been whitened there, but you can see its history here.

Collatz conjecture

External links

• Wikipedia contributors (2017) Collatz conjecture. Wikipedia, The Free Encyclopedia.
• Jeffrey C. Lagarias (v1:2003, v13:2011) The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author), arXiv:math/0309224v13 (math.NT)
• Jeffrey C. Lagarias (v1:2006, v6:2012) The 3x+1 Problem: An Annotated Bibliography, II (2000-2009), arXiv:math/0608208v6 (math.NT)
• Jeffrey C. Lagarias (2010) The Ultimate Challenge: The 3x+1 Problem. American Mathematical Society.
• Terry Tao (2011) The Collatz conjecture, Littlewood-Offord theory and powers of 2 and 3.
• John C. Turner: Paul S. Bruckman and Number Theory
• Amir Zoet, Johan Mogens Følsgaard, Rasmus Krisoffer Pedersen & Kasper Emil Dueholm Freiman (2015) On the strategies used to attack unsolved mathematical problems: a case study of the Collatz Conjecture, Roskilde University
• Collatz project at BOINC

Combinations with repetition

Definition

A combination with repetition is a mapping from a set $A$ into $\left\lbrace 0,1,\ldots ,k\right\rbrace$, such that it assigns to every element in $A$, the number of times that it occurs repeteadly (between $0$ and $k$), under the condition that their sum is $k$.

Theorem

The total number of these combinations with repetition is:

$${\begin{aligned}CR_{n,k}&={\binom {n+k-1}{k}}\end{aligned}}\ \ \ \ \ (1)$$

An alternative notation for $CR_{n,k}$ is $\left(\!\!{\binom {n}{k}}\!\!\right)$.

Interpretations

• $CR_{n,k}$ is the total number of selections, with repetition, of size $k$, from a collection of $n$ objects.
• $CR_{n,k}$ is the total number of multisets of $k$ elements from a set of $n$ elements.
• $CR_{n,k}$ is the total number of ways of distributing $k$ objects among $n$ people.
• $CR_{n,k}$ is the total number of integer solutions of the equation $x_{1}+x_{2}+\cdots +x_{n}=k$, where $x_{i}\geq 0$, for all $i\in \left\lbrace 1,2,\ldots ,n\right\rbrace$.
• $CR_{n,k}$ is the total number of ways of distributing $k$ indistinguishable objects into $n$ distinguishable bins, without any restrictions.

Theorem

Trivially:

$${\begin{aligned}CR_{n,k}&=C_{n+k-1,k}\end{aligned}}\ \ \ \ \ (2)$$

Derivative interpretations, I

• $CR_{n,k}$ is the total number of subsets of $k$ elements from a set of $n+k-1$ elements.
• $CR_{n,k}$ is the total number of paths on a grid of size $k\times (n-1)$.
• $CR_{n,k}$ is the total number of finite sequences of ones and zeros, of length $n+k-1$, that contains exactly $k$ ones and $n-1$ zeros.

Theorem

Trivially:

$${\begin{aligned}CR_{n,k}&=PR_{n-1,k}\end{aligned}}\ \ \ \ \ (3)$$

Derivative interpretations, II

• $CR_{n,k}$ is the total number of surjective mappings from a set $A$ of $n+k-1$ elements into a set of $2$ elements, $B=\left\lbrace b_{1},b_{2}\right\rbrace$, under the following conditions: $n-1$ elements of $A$ have the same image $b_{1}\in B$ and $k$ elements of $A$ have the same image $b_{2}\in B$, where $\left(\forall i,j\right)\left(i\neq j\Rightarrow b_{i}\neq b_{j}\right)$.
• $CR_{n,k}$ is the total number of words of length $n+k-1$ in which it occurs only two letters $l_{1}$ and $l_{2}$ from a certain alphabet, albeit one occurs $n-1$ times and the other is repeated $k$ times.

Divisibility rule

General divisibility rule (base $10$)

Let us consider $k\in \mathbb {Z} ^{+}$, $I=\left\lbrace 0,\ldots ,k\right\rbrace$ and $n=n_{0}+n_{1}\cdot 10+n_{2}\cdot 10^{2}+\cdots +n_{k}\cdot 10^{k}$, where $(\forall i\in I)(n_{i}\in \mathbb {N} \wedge 0\leq n_{i}<10)$. For all $i\in I$, let $r_{i}$ be the $i^{\text{th}}$-potential residue of $10$, modulo $m$, that is, $10^{i}\equiv r_{i}(mod\;m)$. Then: $m\mid n\Leftrightarrow m\mid \left(n_{0}+n_{1}r_{1}+n_{2}r_{2}+\cdots +n_{k}r_{k}\right)$.

General divisibility rule (any base)

Let us consider $k\in \mathbb {Z} ^{+}$, $I=\left\lbrace 0,\ldots ,k\right\rbrace$ and $n=n_{0}+n_{1}\cdot b+n_{2}\cdot b^{2}+\cdots +n_{k}\cdot b^{k}$, where $(\forall i\in I)(n_{i}\in \mathbb {N} \wedge 0\leq n_{i}<b)$. For all $i\in I$, let $r_{i}$ be the $i^{\text{th}}$-potential residue of $b$, modulo $m$, that is, $b^{i}\equiv r_{i}(mod\;m)$. Then: $m\mid n\Leftrightarrow m\mid \left(n_{0}+n_{1}r_{1}+n_{2}r_{2}+\cdots +n_{k}r_{k}\right)$.

External links

• Robert T. Kurosaka (1986) Mahematical Recreations: Euclid's Algorithm (GCDs, LCMs and repeating decimals). In: Byte Magazine Volume 11 Number 01: Robotics (from https://archive.org/details/byte-magazine)
• Base-n Conversion Calculator
• The Dozenal Society of America

Inverting programs

Concepts

Inverse programming gets information about any product available to the public. When we apply it to skip software protections is usually called Cracking. This engineering tries to take an element, a determinated product, to study its behaviour and composition and duply a program faithfuly.

This method is called that way because it proceeds in the inverse direction of the usual ingineering tasks, which consists in using technical data to elaborate a determinated product.

Generally if the product or another material which was submtted to inverse programming was obtained properly, then the process is legal. In the same way, generic products made with this technique can be legally distributed .

Samba is an example of this kind of engineering as it lets operative systems UNIX to share archives with Windows systems. Samba proyect had to investigate confidential information about technical aspects related with Windows O.S. WINE is another example, which works with Windows’ API and OpenOffice.org with Microsoft Office formats. It is also made to understand NTFS archive system structure so it can be possible to develop drivers to read and write upon itself. (mainly for GNU/Linux based systems).

Inverse programming is a resolution method. Applying it to something suppose to deepen in the study of its operation until we cand understand, modify and improve it.

Examples

An example of a program which is, at the same time its inverse program can be easyly implemented on Python. This example requires a password and a sentence to encrypt. Then it execute F[i] XOR C[i |L|] (L = length(C)). If the operation is repeated on the result of F', F is obtained again.

text = input('Insert your sentence: ')
pword = input('Insert your password: ')

#At first sight, we change the strings to numbers

f_num = [ord(c) for c in text]
f_pass = [ord(c) for c in pword]

#Then, we apply the XOR operator to the data

f_res = [f_num[i] ^ f_pass[i % len(f_pass)] for i in range(len(f_num))]
result = ''.join([chr(n) for n in f_res])


print(result)

Bibliography

• David Gries, "The Science of Programming", Chapter 21: Inverting Programs
  

External links

• Rustan, K., Leino, M., 1994, Computing permutation encodings, sección 2.4: «Inverting the program», California Institute of Technology, Pasadena, CA, USA, http://authors.library.caltech.edu/26789/1/postscript.pdf

Newton’s divided-difference interpolating polynomials

External links

• Wikipedia contributors (2003ff.) Newton polynomial. Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Newton_polynomial
• A. K. Dewdney on The Internet Archive
  • The Tinkertoy Computer and other machinations (Chapter 17: Automated Mathematics)
• Sequence solver, by AlteredQualia
• Leon Q. Brin (2016) Tea Time Numerical Analysis. Experiences in Mathematics, 2nd ed., CC BY-SA (§ 3.3)
• Steven C. Chapra & Raymond P. Canale (2010) Numerical methods for Engineers, McGraw-Hill Science/Engineering/Math, 6th ed., ISBN: 9780072918731, § 18.1, http://openlibrary.org/books/OL7305712M/Numerical_Methods_for_Engineers
• Steven C. Chapra & Raymond P. Canale (2007) Métodos numéricos para ingenieros, 5ª ed., § 18.1
• Steven C. Chapra & Raymond P. Canale (2010) Numerical methods for Engineers, 6th ed., § 18.1 / Steven C. Chapra & Raymond P. Canale (2007) Métodos numéricos para ingenieros, 5ª ed., § 18.1
• Walter Mora (2016) Introducción a los métodos numéricos (§ 2.6 ff.)
• Ibáñez Pérez, María José, Notas sobre Interpolación polinómica

Permutation generation methods

Listing in lexicographic order

Let $\left\lbrace a_{1},\ldots ,a_{n}\right\rbrace$ be a set of labels (letters, numbers...) for the objects, so distinguishables.

Lexicographic order:

$$\left(\sigma _{i}(a_{1}),\ldots ,\sigma _{i}(a_{n})\right)\prec \left(\sigma _{j}(a_{1}),\ldots ,\sigma _{j}(a_{n})\right)\Leftrightarrow \exists k\in \lbrace 1,\ldots ,n\rbrace ,{\begin{aligned}\sigma _{i}(a_{1})&=\sigma _{j}(a_{1})\\&\wedge \\\sigma _{i}(a_{2})&=\sigma _{j}(a_{2})\\&\wedge \\&\vdots \\&\wedge \\\sigma _{i}(a_{k-1})&=\sigma _{j}(a_{k-1})\\&\wedge \\\sigma _{i}(a_{k})&<\sigma _{j}(a_{k})\end{aligned}}$$

Generating the next permutation in lexicographic order:

Note that:

If $\sigma _{i}(a_{n-1})<\sigma _{i}(a_{n})$, then, $\operatorname {swap} \left(\sigma _{i}(a_{n-1}),\sigma _{i}(a_{n})\right)$.

For example, 1234576 follows to 1234567 in the sequence.

If $\sigma _{i}(a_{n-1})>\sigma _{i}(a_{n})$, then,

if $\sigma _{i}(a_{n-2})<\sigma _{i}(a_{n-1})$, then,

put $\min(\sigma _{i}(a_{n-1}),\sigma _{i}(a_{n}))$ at position $n-2$, placing $\max(\sigma _{i}(a_{n-1}),\sigma _{i}(a_{n}))$ and $a_{n-2}$ at positions $n-1$ and $n$ in increasing order.

For example, 1234657 follows to 1234576 in the sequence.

Target:

Deduce the method for the general case.

See also

• Permutation

More

• Robert Sedgewick. Permutation Generation Methods. Computing Surveys, Vol 9, No 2, June 1977, pp. 137-164. http://homepage.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf
  • (Lexicographic algorithms: pp. 152ff.)
• Permutations: sequence A000142 at the OEIS.

RSA (cryptosystem)

RSA (Rivest, Shamir, Adleman, 1978).

Explorations and tools

• Wolfram|Alpha
• factordb.com
• nettle
• ius/rsatool
• Understanding Common Factor Attacks: An RSA-Cracking Puzzle
• Understanding Common Factor Attacks (programming element)
• RSA Encryptor/Decryptor/Key Generator/Cracker

Programming

• repl.it

See also

• Ethical hacking (Wikipedia contributors, "Ethical hacking," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Ethical_hacking) (En Epistemowikia, aquí)
• Integer factorization (Wikipedia contributors, "Integer factorization," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Integer_factorization)
• RSA (cryptosystem) (Wikipedia contributors, "RSA (cryptosystem)," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/RSA_(cryptosystem))
• RSA Factoring Challenge (Wikipedia contributors, "RSA Factoring Challenge," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/RSA_Factoring_Challenge)
• Shor's algorithm (Wikipedia contributors, "Shor's algorithm," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Shor's_algorithm)

External links

• Gianluca Dini (2016) The RSA cryptosystem

Transitive closure of a binary relation

Introduction

There is an operation called closure in the binary relation. The idea of closure is to construct a new binary relation R’of R by adding some ordered pairs, which makes R' have some special properties such as reflexivity, symmetry and transitivity. Transitive closure is an important content of binary relations, which plays an important role in many fields such as the fundamentals of compiling, formal language and automaton.

History

The calculation of transitive closure of binary relation generally according to the definition. This method needs a number of compound set calculation, which is very prone to accidents. In 1962, Warshall proposed an efficient algorithm for computing transitive closures. The Warshall algorithm is simple and easy to implement in the computer, but it uses more time to calculate^[2]. In recent years, many scholars proposed improved algorithms of transitive closure. There are algorithms simplify the calculation of the original transitive closure through reducing the number of relation compound^[3-4]. Some algorithms use the relational matrices to calculate, also simplifies the calculation of transitive closure^[5-6].

Concepts

Let R be the relation on the nonempty set A, relation R’ of A is the transitive closure of R if and only if R’ satisfies: (1) R’ is transitive; (2) R⊆ R’; (3) For any transitive relation R’’ of A include R, there have R’⊆ R’’. We usually use t(R) to represent the transitive closure of R.

State of the art

The transitive closure of a binary relation always exist, any binary relation can be extended until the extended relation is transitive. Besides the transitive closure that we denot here admits a very simple characterization

Practical applications

In Nuutila (1995) we can find useful algoriths to calculate the transitive closure of a graph. Metods are in the worst case faster and reduce the problem to a "simple" matrix multiplication. The problem can be resolved by the Floyd-Warshall algorithm, or by extended search of width-first or depth-first search starting from each node in the graph. Recent research has explored a new efficient methods to calculate a transitive closure in distributes systems based on the MapReduce paradigm (Afrat et al.,2011)

• Floyd-Warshall algorithm:

It is a graph analysis algorithm to find the most efficient way to do weighted directed graphics. The Floyd-Warshall algorithm compares all possible paths across the graph between each pair of vertices. It does this by gradually improving an estimate of the shotest path between two vertices, until it is know that the estimate is optimal

References

• [1]M Yang. Methods on The Transitive Closure of Binary Relation[J]. Network Security Technology and Application, 2006 (04):48-49+84.
• [2]X Wang. An Algorithm for the Transitive Closure Based on Setting Compound Position[J]. Journal of Suzhou University of Science & Technology, 2014 (3):43-45.
• [3]X Chen. On Transitivity and Transitive Closure for Binary Relation[J]. Mathematics in Practice and Theory, 2004,34(9):135-137
• [4]L Zhai, W Xie. The Computation on Transitive Closure[J]. Journal of Henan Institute of Education, 2005, 14(1):25-26.
• [5]X He, H Wang. A Method to Find the Transitive Closure of a Relation by Matrix[J]. Mathematics in Practice and Theory, 2005, 35(3):172-175.
• [6] F Su, A Resolution about the Transitive Closure Based on The Relation to the Matrix in Limited Collection[J]. Natural Science Journal of Harbin Normal University, 2007, 23(6):22-24

Bibliography

• Wikipedia contributors. "Transitive closure." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 31 Jan. 2017. Web: https://en.wikipedia.org/w/index.php?title=Transitive_closure&oldid=762903855. 27 Feb. 2017.

External links

Union-find algorithms for sets

Introduction

In computer sciences, a union-find algorithm is a data structure that keeps trackof a set of elements partitioned into a number of disjoint subsets.

History

Union-find algorithms were first described by Bernard A. Galler and Michael J. Fischer in 1964. In 1973, their time complexity was bounded to $\Omega (log^{*}(n))$, the iterated logarithm of $n$, by Hopcraft and Ulllman. In 1975, Robert Tarjan was the first to prove the $O(\alpha (n))$ upper bound on the algorithm's time complexity. In 1989, Fredman and Saks showed that $\Omega (\alpha (n))$ words must be accessed by union-find algorithms per operation.

Bibliography

Disjoint-set data structure, English Wikipedia

External links

• Robert Sedgewick, Princeton University, https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

See also

Inner links

• Participants and major contributions of the university project, learning plan and sandbox of the learning plan
  • University project 'Discrete and numerical mathematics'
  • University project 'Discrete and numerical mathematics': Participants and major contributions
  • Learning plan 'Discrete and numerical mathematics'

• Talk pages
  • Talk page of the university project 'Discrete and numerical mathematics'
  • Talk page of the page of the participants and major contributions of the university project 'Discrete and numerical mathematics'
  • Talk page of the learning plan 'Discrete and numerical mathematics'
  • Talk page of the sandbox of the learning plan 'Discrete and numerical mathematics'

Interwiki links

• University project, participants and major contributions, learning plan and sandbox of the learning plan
  • University project 'Matemática discreta y numérica' (equivalent university project on the Spanish Wikipedia)
  • University project 'Matemática discreta y numérica': participant and major contributions (equivalent university project [partipants and major contributions page] on the Spanish Wikipedia)
  • Learning plan 'Matemática discreta y numérica' (equivalent learning plan on the Spanish Wikipedia)
  • Sandbox of the learning project 'Matemática discreta y numérica' (sandbox of the equivalent learning plan on the Spanish Wikipedia) (editathons are here)

• Talk pages
  • Talk page of the university project 'Matemática discreta y numérica' (talk page of the equivalent university project on the Spanish Wikipedia)
  • Talk page of the page of the participants and major contributions of the university project 'Matemática discreta y numérica' (talk page of the page of the participants and major contributions of the equivalent university project on the Spanish Wikipedia)
  • Talk page of the learning plan 'Matemática discreta y numérica' (talk page of the equivalent learning plan on the Spanish Wikipedia)
  • Talk page of the sandbox of the learning plan 'Matemática discreta y numérica' (talk page of the sandbox of the equivalent learning plan on the Spanish Wikipedia) (editathons, in Spanish, are here)

To keep track, know more or write a comment

• Talk page of the sandbox/workshop of the learning plan 'Discrete and numerical mathematics'.

About this page on the English Wikipedia

• Wikipedia:School and university projects/Discrete and numerical mathematics/Learning plan/Sandbox (edit | talk | history | links | watch | logs)