# Tagged Questions

45 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 ...
28 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: ...
351 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 + ...
88 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 ...
70 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 ...
335 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 ...
428 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 ...
138 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 ...
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 ...
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 ...