Tagged Questions

0
votes
0answers
10 views

Number Theoretic Gaps for Shell Sort

Has anyone investigated the efficiency of certain number theoretic gaps for shell sort? I'm thinking the Fibonacci sequence may be interesting, or maybe the prime numbers since small coprime sets ...
5
votes
1answer
124 views

Mathematical way of determining whether a number is an integer

I'm developing a computer program, and I've run into a mathematical problem. This isn't specific to any programming language, so it isn't really appropriate to ask on stackoverflow. Is there any way ...
1
vote
0answers
84 views

Question about the elementary divisors of a special matrix

I have the following question: Is there a closed formula for the elementary divisors of the Matrix $M={(m_{ij})}_{i=1,...,n,\ j=1,...,k}$, where ${m}_{ij}$ is the greates common divisor of $i$ and ...
4
votes
0answers
110 views

Is there a polynomial-time algorithm to find a prime larger than $n$?

Is there a polynomial-time algorithm to find a prime larger than $n$? If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
1
vote
1answer
145 views

question on how to decrypt the message

A message is encrypted using an affine cryptosystem in which plaintext uses the 26 letters A through Z (all blanks are omitted), the letters are identified with the residue classes of integers (mod ...
0
votes
0answers
88 views

Is there an emirp greater than $10^{10006}+941992101 \times 10^{4999}+1$?

An emirp is a prime such that a distinct prime is formed when its digits are reversed. According to Wikipedia (and its references), the largest known emirp is \[p:=10^{10006}+941992101 \times ...
1
vote
1answer
64 views

Algorithm to find nearest quotient in $\mathbb{Z}[i]$

Given two Gaussian integers $x$, $y$ what's the fastest way to find the Gaussian integer $z$ which minimizes $|x - zy|$? Then this Gaussian integer can be taken as $z = x/y$.
1
vote
1answer
134 views

Largest number definable

If $a_n$ is defined as the largest integer definable using $n$ characters in some standard theory like PA or $Z_2$. Can we prove or disprove that there is some finite integer $k$, such that for all ...
3
votes
1answer
81 views

What algorithms are there for determining whether a Gaussian integer is prime?

Give a Gaussian integer $z\in{Z[i]}$, how can I determine if $z$ is prime? I imagine there exists an algorithm that maps primality in $Z[i]$ to primality in Z. And for the case when $z\in{Z}$ I think ...
0
votes
2answers
161 views

Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$

The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$ Normally one can use the "baby-steps giant-steps" algorithm to solve it fairly quickly. ...
5
votes
0answers
82 views

$X^A \equiv B \pmod{2K + 1}$

I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$. Is there something special about the modulus being odd that allows us to ...
15
votes
5answers
775 views

What interesting open mathematical problems could be solved if we could perform a “supertask” and what couldn't?

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved ...
3
votes
1answer
241 views

Properties of computable numbers

If we enumerate* all the computable numbers, those for which there exist a turing machine that outputs its digits to arbitrary precision. What is known about the asymptotic density of rationals, ...
5
votes
2answers
3k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
1
vote
1answer
316 views

CRC computation

I would like to understand the CRC computation using CCITT CRC-16 $x^{16} + x^{12} +x^{5} +1$. I was able to successfully implement it in a program but I would like to understand the computation ...
13
votes
3answers
364 views

Curious Properties of 33

Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to: The Bernstein Hash method uses the number 33 as a multiplier. From what ...
8
votes
2answers
138 views

Given $N$, count $\{(m,n) \mid 0\leq m<N, 0\leq n<N, m\text{ and } n \text{ relatively prime}\}$

I'm confused at exercise 4.49 on page 149 from the book "Concrete Mathematics: A Foundation for Computer Science": Let $R(N)$ be the number of pairs of integers $(m,n)$ such that $0\leq m < N$, ...
3
votes
1answer
114 views

Prove or refute that $\frac{t^a-1}{t^b-1}$ is not a integer if $a \mod b \neq 0$

Hi guys in my last question I got the wrong idea maybe because a poor problem's description or maybe because of my poor English skills. So, anyway I found out the problem requires to be a integer. ...
3
votes
2answers
181 views

Prove or refute that $\frac{t^a-1}{t^b-1}$ has more than 100 digits if $a \mod b \neq 0$

I'm a computer science student from Mexico and I have been training for the ICPC-ACM. So one of this problems called division sounds simple at first. The problem is straight for you have and 3 ...
3
votes
1answer
77 views

An efficient way to check whether a polynomial (under certain condition) is absolutely equal to zero or not

We have a function $f$ of $N$ variables which is the product of $M$ polynomials: $$f(x_1,x_2,\ldots, x_N) = P_1 \cdot P_2 \cdots P_M.$$ Each $P_i$ is a polynomial of at most three variables ...
0
votes
1answer
64 views

Minimum number of numbers to be inserted in a sequence to transform it into an A.P

Given a sequence of N numbers, how can we find the minimum number of numbers to be inserted to make this sequence to an Arithmetic progression.(we can insert at any position of this sequence) For ...
1
vote
3answers
804 views

What are the prerequisites for combinatorics?

I'm looking to strengthen my understanding of the math that is directly useful to practical computer science, as opposed to unsolved computer science problems. In other words, the kind of math that ...
2
votes
2answers
281 views

'(Pseudo)-random functions' by seeding of PRNGs?

I have an application that wants controllable random functions from $\mathbb{Z}^2$ and $\mathbb{Z}^3$ to $2^{32}$ , where by controllable I basically mean seedable by some parameters (say, on the ...