All Questions
Tagged with computer-science nt.number-theory
49 questions
5
votes
1
answer
469
views
Is the set of generalized Fermat triples computable?
Is $\;\big\{(a,b,c)\in\mathbb{N}^3: \big(\exists m,n,\ell \in (\mathbb{N}\setminus\{0,1,2\})\big): a^m + b^n= c^\ell\big\}\;$ computable?
- 48.9k
9
votes
1
answer
1k
views
1
vote
0
answers
78
views
On binary constraints defined by vanishing of bivariate polynomials modulo $n$ [duplicate]
In an answer here
Dima Pasechnik showed that constraints of the form $x_i x_j + a_{ij}x_i + b_{ij}x_j + c_{ij}$ are efficiently solvable modulo $2$ using Groebner basis.
In comments he suggested that ...
- 25.4k
4
votes
2
answers
320
views
Approximating a fraction with a given denominator
Let $M$, $N$ be large natural numbers (say ~200 bits). Let $L$ be a smaller number, (say ~100 bits).
I want to approximate the fraction:
$$\frac{M}{N} \sim \frac{k}{L+r}$$
where $r$ is at most $L$. In ...
- 591
8
votes
1
answer
677
views
How "correct" is Knuth's fast addition $(a,b) \mapsto (a \oplus b) \oplus ((a\land b) \ll 1)$?
Donald Knuth suggested a bitwise approximation for addition on the non-negative integers that is very fast on common processors:
$(a,b)\mapsto (a\oplus b) \oplus ((a\land b) \ll 1)$,
where $a,b$ are ...
- 48.9k
4
votes
1
answer
291
views
Discrepancy in the calculation of $2$-Selmer group by Magma and LMFDB
The result of LMFDB claims (https://www.lmfdb.org/EllipticCurve/Q/1640/c/1 )
that (2-part of) Tate-Shafarevich group $\mathrm{Sha}(E/\Bbb{Q})$ of elliptic curve $y^2=x^3-8747x-314874$ has order $16$. ...
- 1,531
1
vote
0
answers
64
views
Does Frobenius number increase if bound on input increases?
The Frobenius number F is the largest number not expressible as a non-negative linear combination of some set of positive integers $\{a_i\}$, where, $a_i$ has gcd 1. Denote $maxF(n)$ as the maximum of ...
3
votes
1
answer
167
views
Is factorial computation known to be in a class smaller than $FEXP$?
Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
- 13.9k
5
votes
1
answer
264
views
Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1)$
Motivation. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b "=...
- 48.9k
1
vote
0
answers
62
views
Polynomial sized arithmetic map from circle to ellipse preserving integral points
Let $n$ be a square free integer and a product of $O(m/\log m)$ number of primes $1\bmod 4$ where $m$ is $\log_2n$.
Take the circle around origin of radius $n^2$. It has ${\exp}(m/\log m)$ number of ...
- 13.9k
7
votes
2
answers
779
views
Does there exist a process to build a list of numbers whose standard deviation is an integer?
Or rephrased, is there a way to make a list of numbers whose sample variance is a square number? I'm interested in sequences of arbitrary length with integer elements.
(I come from a computer science ...
- 79
2
votes
0
answers
77
views
Iterated removal of singleton Pythagorean triples
Consider the set of all Pythagorean triples (positive integers $a, b, c$ such that $a^2 + b^2 = c^2$, not necessarily coprime). Then for each integer that appears in exactly one triple, remove that ...
- 130
4
votes
1
answer
498
views
Large radical of an integer and three AB conjectures
In this Note, We propose a new definition called "large radical of an integer". Using this definition, three very useful $AB$ conjecture are given.
1. Large counter examples of the ABC conjecture
...
- 1,776
0
votes
1
answer
81
views
Normal $0,1$-sequence with infinitely many frequent finite substrings
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
- 48.9k
0
votes
3
answers
1k
views
Given $N$ integers on a circle, how to choose them in pairs to obtain minimum sum?
(Added by YCor 2019 July 7): it has been mentioned in the comments that this is part of a contest "Circular merging, July Challenge 2019 Division 1", where an equivalent question (just more clearly ...
user142755
2
votes
1
answer
152
views
Computationally random bitstreams and normalcy
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
- 48.9k
4
votes
1
answer
375
views
$\sum_{i=1}^x\sum_{j=1}^xf(i\cdot j)$ Double Summing a (Not Completely) Multiplicative Function
Let $f(n)$ be a multiplicative function that is not completely multiplicative, i.e $f(m)\cdot f(n)= f(m\cdot n)$ only if $gcd(m,n)=1$. Let $S(x)$ be the double sum over $f$, that is:
$$S(x)=\sum_{i=1}...
- 311
9
votes
0
answers
2k
views
Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere
Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
- 311
4
votes
0
answers
274
views
What arithmetic would you do in parallel?
This is a post asking for references, and soliciting problems and people interested in accelerated computing. I will add the big-list tag and make it community-wiki. If this interests you strongly, ...
7
votes
1
answer
285
views
Coefficients of linear dependency
Let $L_1, \ldots, L_m \in \mathbb{Z}[x_1, \ldots, x_n]$ be polynomials of the form $L_i = l_{i1} \cdot l_{i2} \ldots \cdot l_{ik}$, where every $l_{ij}$ is an integer linear form.
Assume that ...
- 2,576
6
votes
0
answers
176
views
Approximating a ray with an integer lattice point
Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r^2\}.$
With $\|\cdot \|$ the 2-norm, what is the distribution (or at least the ...
10
votes
0
answers
4k
views
Is the conjecture A+B=C following correct?
Is the conjecture on A+B=C following correct ?
Conjecture: Let $A, B, C$ be three positive integer numbers such that $A+B=C$ with $\gcd(A, B, C) = 1$. By Fundamental theorem of arithmetic we write:
$...
- 1,776
2
votes
2
answers
169
views
Decidability of matrix problem in ${\mathbb Z}/p{\mathbb Z}$
Let $p$ be a prime number, $n$ be a positive integer, and let ${\mathbb Z}_p^{n\times n}$ denote the set of $n\times n$-matrices over ${\mathbb Z}/p{\mathbb Z}$.
Suppose we are given an integer $m>...
- 48.9k
4
votes
1
answer
588
views
Another conjecture on sum $A+B=C$
Could You give your ideas, your comment, or a referen for a conjecture as follows:
Consider $A, B, C$ be three positive integers numbers. By Fundamental theorem of arithmetic we write:
$A=a_1^{x_1}...
- 477
4
votes
1
answer
207
views
Nearly De Bruijn sequences constructed from De Bruijn sequences
Let $w$ be a De Bruijn $01$-sequence of the type $B(2,n)$; i.e., a cyclic $01$-sequence that contains every $n$-digit $01$-sequence exactly once. Let $x$ be a $01$-sequence of length $n$. When and ...
- 3,443
1
vote
0
answers
123
views
Expressing Numbers with a Minimal Sum in Powers of 2 [closed]
The first 64 bits of pi are:
11.00100100001111110110101010001000100001011010001100001000110100
Computer multiplication can be sped up by looking for patterns and ...
- 1,547
5
votes
2
answers
500
views
How to construct particular De Bruijn sequences
For $n \ge 2$, there is at least one binary DeBruijn sequence beginning with $n$ zeros followed by $n$ ones. Is there a straightforward way to construct such a sequence for each $n \ge 2$? Examples:
...
- 3,443
3
votes
1
answer
382
views
Equivalence between Diffie Hellman and Discrete Log
For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...
user76479
4
votes
0
answers
311
views
Possible $\mathsf{NP}$ complete problem from number theory
A candidate $\mathsf{NP}$ complete variant of factoring was posted in https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem $\text{BOUNDED-...
- 13.9k
14
votes
1
answer
3k
views
Can Shor's Algorithm be modified to run efficiently on a classical computer?
Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...
- 2,649
11
votes
3
answers
8k
views
How to calculate the sum of remainders of N?
I'm trying to sum the remainders when dividing N by numbers from $1$ up to $N$
$$\sum_{i = 1}^{N} N \bmod i$$
It's easy to write a program to evaluate the sum if N is small in $O(N)$ but what if N is ...
- 233
5
votes
1
answer
275
views
How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?
First some
Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...
- 7,127
4
votes
2
answers
1k
views
When does the greedy change-making algorithm work?
The change-making problem asks how to make a certain sum of money using the fewest coins. With US coins {1, 5, 10, 25}, the greedy algorithm of selecting the ...
- 163
6
votes
1
answer
352
views
Number of partitions whose blocks form arithmetic progressions
As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$. ...
- 24.8k
5
votes
1
answer
327
views
Subsets of all Diophantine's sets
I have asked this question on math.stackexchange already:
https://math.stackexchange.com/questions/627461/subsets-of-all-diophantines-sets
Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\...
- 2,576
12
votes
1
answer
4k
views
How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?
Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
...
- 241
23
votes
5
answers
1k
views
Securing privacy of "who communicates with whom" under Orwell-like conditions
Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...
- 19.6k
1
vote
1
answer
324
views
Problem to a solution
Consider an NP hard problem $\frak P$ which takes an input of length n
$\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...
- 11
3
votes
1
answer
296
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=\lbrace (m_{ij})\rbrace_{i=1,...,n,\ j=1,...,k}$, where $m_{ij}$ is the greatest common ...
3
votes
1
answer
1k
views
Collatz conjecture— finite state machine transducer construction, origination?
wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer computing sequential ...
- 529
5
votes
2
answers
2k
views
How to draw Archimedean-Galileo spiral?
It is known that some plane curves can be drawn with a tool. For instance, I heard at a web site that Archimedes created his spiral in the third century B.C. by fooling around with a compass and ...
1
vote
1
answer
288
views
Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without "being able to know" one of the discrete logs involved (formal definition given in question)?
Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ...
19
votes
3
answers
1k
views
Status of an open problem about semilinear sets
In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem:
Find a decision procedure for determining if an arbitrary semilinear set
is a ...
- 373
4
votes
1
answer
4k
views
How are taps proven to work for LFSRs?
Obviously, you can exhaustively check that it lands on every state except the zero state, but for large linear feedback shift registers (LFSR), this quickly becomes infeasible.
Wikipedia states the ...
- 149
1
vote
4
answers
2k
views
What is the name of the function f(x,y) = ((x-1) mod y)+1 ?
Does the function $f(x,y) = ((x-1) \mod y)+1$ have an existing name?
f(1,5) = 1
f(2,5) = 2
...
- 339
3
votes
2
answers
912
views
Why is every finite set Diophantine? [closed]
I understand that every finite set is recursively enumerable, as I see that one could just encode each element of some finite set on a Turing Machines tape, and then have the machine check each member ...
3
votes
1
answer
2k
views
Conditions that allow unique solutions for Linear Diophantine equations
(This posting became very long, so I should note that there are two alternative but nearly equivalent formulations of the same question being given. The first one asks for the optimal strategy for ...
5
votes
3
answers
4k
views
Counting lattice points on an n-simplex
Imagine an n-simplex, the solution set for the expression: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, where:
$a_1$ through $a_n$ are positive bounded integers
$x_1$ through $x_n$ are ...
1
vote
1
answer
210
views
Extracting integer multiplicative factors from the sum of certain sets of (finite-precision) real numbers?
Update based on Michael's answer (thanks again!) - Can the LLL or PSLQ algorithms provide a (knowably - i.e. not just incidental) unique solution for the set of integer multiplicative factors? Are ...
- 43