1
vote
1answer
44 views

Odd way to do arithmetic

If I want to divide $9251$ by $29$, the methods taught in elementary school suffice. Now suppose I want the prime factorization of $9251$. The square root of that number is between the consecutive ...
0
votes
0answers
27 views

Positive Arithmetic Complexity

Define the binary operator $[k]$ as an operator that takes an integer $k$ and operates between two integers $a,b$ such that: $$a[k]b = (...((((a)[k-1]a)[k-1]a)[k-1]...a)[k-1]a$$ (b times) And: ...
6
votes
1answer
268 views

How to find an expression whose value is 190

Given a set of numbers (in this case): 3, 7, 7, 100, 50 Either: prove it is impossible to form the number k = 190 using ( ) + - * / operators between sub set of the these numbers ex: 1000 = ((3 + ...
0
votes
0answers
86 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I asked: we treat all inputs and intermediate results and final outputs as ...
0
votes
2answers
68 views

Can all programs be modeled as operations of elementary arithmetic operations on inputs?

In mathematics and computabiltiy theory, we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we ...
2
votes
3answers
313 views

Factoring extremely large integers.

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
6
votes
2answers
346 views

Time complexity to calculate a digit in a decimal

As we know, it is quiet fast to calculate any digit in a rational number. For example, if I'm given 1/7 (0.142857 142857 ...) and any integer K, I could easily return the Kth digit of 1/7, by doing a ...
2
votes
2answers
137 views

Sum set fixpoint, how many iterations?

I want to approach linear equations of the following form over the integers $\mathbb{Z}$: $$x_1 + \cdots + x_n = 0.$$ I stepped over the sum set, which is defined as follows: $$S + T = \{ x + y ...
9
votes
2answers
404 views

How hard is it to do arithmetic?

People in computing are often observed saying that a computation takes $\operatorname{O}(n^3\log n)$ steps or that it's NP-hard or that it's not computable, or that it's primitive recursive, etc. I ...
5
votes
2answers
311 views

Is there a log-space algorithm for divisibility?

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...