0
votes
0answers
45 views

How to simplify following equation?

Here is the equtation: $$\mathrm{P} = \prod_{1\le i \le n}(a_i+1)^2+\left(\sum_{1\le i \le n}a_i\right)\prod_{1\le i \le n}(a_i+1)+\sum_{1\le i \le n}a_i^2-1$$ It is hard to compute each $a_i$, but I ...
1
vote
1answer
31 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
0
votes
2answers
66 views

Existing Algorithm / Code to calculate exact values of the Riemann Zeta function at even natural numbers?

I wanted to know if there's any existing algorithm to compute exact values of the Riemann Zeta function at even natural numbers? For example, it should compute $\zeta(4)$ as exactly $\frac{\pi^4}{90}$ ...
0
votes
2answers
72 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
3
votes
2answers
41 views

$(2^a -1)(2^b -1)=2^{2^c}+1$ has no nonnegative integer solutions

$(2^a -1)(2^b -1)=2^{2^c}+1$ is not possible for a,b,c nonnegative integers. Any solutions using parity Approach: $(2^a -1)(2^b -1)=2^{2^c}+1\Rightarrow$ $2^{a+b}-2^a-2^b=2^{2^c}\Rightarrow$
2
votes
1answer
58 views

Designing a turing machine

Suppose you have a tape that has a block of $a$ strokes followed by a space, followed by a block of $b$ strokes, followed by a space, followed by a block of $c$ strokes, and otherwise blank. ...
5
votes
2answers
91 views

Relatively prime property verification

I am reading a computer science puzzles book. And I get the following question - "You have a five quart jug, a three quart jug and unlimited supply of water. How would you come up with exactly four ...
3
votes
1answer
102 views

An alternate analysis to the (worst-case) run time of the euclidean algorithm

I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci ...
2
votes
1answer
29 views

Strong primes in cryptography, their relation to complexity theory and security

According to the lecture slide by Shafi Goldwasser a prime is a strong prime if: $$p = 2q + 1$$ for some prime q. For me it, seems a bit arbitrary that is the definition of a strong prime in ...
2
votes
1answer
137 views

Subsets of all Diophantine's sets

Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\Leftrightarrow$ graph of function is Diophantine. Consider some subset $S$ of computable functions (for example some Grzegorczyk's class or ...
0
votes
1answer
32 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
3
votes
1answer
65 views

How does the math in the RSA trapdoor work?

You have the candidate one-way function $$f_{n,e}(x) = x^e \mod n,$$ where $n = pq$ with $p,q$ primes with $|p| = |q|$ (same bit length) and $\gcd(e, (p-1)(q-1)) = 1$. Then the trapdoor, that is, ...
5
votes
0answers
121 views

How to list the prime factorised natural numbers?

Today I set out to invent a two character numeral system designed to make factorization trivial. Indeed, it lets one factor non-trivial numbers with over thousand digits within 30 seconds per hand - ...
-3
votes
1answer
387 views

Is solving the PvsNP example question a solution to PvsNP?

This example question was created by the claymath institute. The PvsNP question states, suppose the dean leaves you with a task to house a group of 400 students inside dorms. But there is only enough ...
0
votes
0answers
58 views

Please explain the unsolved 3-sat math problem as easy as possible for someone with only basic math skills [duplicate]

I know only basic math like so: (+,-,x,\,). And I know a little bit of programming up to the point of Boolean values.I desperately want to understand the 3-sat question fully so I can solve it, but ...
2
votes
0answers
93 views

Modular Inverse over some given finite field. Which method is more efficient?

I'm trying to do division in some given finite field (let's say mod p). I have 2 Python methods here that are currently doing that, but I'm not sure which is better or if 1 or both is simply wrong. ...
15
votes
1answer
294 views

How to prove there are no more positive integers that are products of 2 and 3 consecutive numbers?

$6$ and $210$ share the property that both are the products of both two and three consecutive numbers. $6$ is $2\times3$ and $1\times2\times3$ and $210$ is $14\times15$ and $5\times6\times7$. It was ...
0
votes
0answers
29 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 ...
6
votes
2answers
282 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
122 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
1answer
260 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
288 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
131 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
65 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
146 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
93 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
205 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
91 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 ...
17
votes
5answers
853 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
285 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
4k 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
585 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
443 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
159 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
121 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
192 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
88 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
68 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
1k 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
301 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 ...