# Tagged Questions

341 views

### Are there any patterns in simple continued fraction expansions of algebraic real numbers?

As we know there are patterns in simple continued fraction expansion of quadratic algebraic numbers,are there any patterns in simple continued fraction expansions of other algebraic real ...
132 views

475 views

189 views

### Choosing a base where a given digit of a given number appears the most times

Is there an algorithm for choosing a base where a given digit of a given number appears the most times, that works better then trial and error? (see also this)
253 views

### Computing the ratio of two large integers modulo m

$P(n)$ and $D(n)$ are two large integers. Suppose $R(n) = \frac{P(n)}{D(n)}$ is an integer. I want to compute $R(n)\bmod m$. $P(n)$ and $D(n)$ are too large to be computed but $P(n)\bmod m$ and ...
1k views

### The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ? I tried going through this paper, but I couldn't understand the procedure. Thanks
2k views

### Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote: "This scheme will thus work as ...
275 views

### Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it. My question is as follows. Given a positive integer $k$, determine a set of properties ...
771 views

### The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function

I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function. Preliminary: Mertens function and the ...
932 views

### Mertens' function in time $O(\sqrt x)$

This MathOverflow question seems to indicate that the state of the art in computing $$M(x)=\sum_{n\le x}\mu(n)$$ takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...
669 views

### Find the maximum set whose subset sum is unique for every of its subset.

We are given a set of $n$ positive integers. We assume all of them are bounded by a polynomial of $n$. We would like to find a subset $S$ of numbers such that for any $T_1,T_2\subseteq S$, the sum of ...
598 views

### How this set of functions is ordered?

Notation: $k, m, n$ are non-negative integers $f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$ $f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$ $f \prec g$ means ...
3k views

### Fastest Algorithm to Compute the Sum of Primes?

Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of ...
310 views

### Feasibility of linear equations with few variables mod k

Say I want to verify the feasibility of $$Ax \equiv b \text{ (mod } k)$$ where $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m}$ and $k \in \mathbb{N}$. Is there a fast way to verify if there ...
288 views

### Algorithm for keeping a concrete version of Euclid's argument simple

(A version of this same question was posted to stackexchange.) Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...
395 views

### Find the least prime $p$ such that $mn$ divides $p-1$

My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice. Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ ...
147 views