# Tagged Questions

1answer
31 views

### Computing the period of a fraction polynomial in the number of digits

So I have a fraction a/b that is known to be repeating. How do I compute the period of the repeating decimal in polynomial-time in the number of digits of A and B?
1answer
98 views

### How to show that Eratosthenes sieve algorithm has a complexity of $O(n\log n)$

I know this is a loose upper bound, but I am in an entry level CS course that is just trying to get us used to evaluating algorithms. Any pointers on how to move forward on this problem?
0answers
54 views

### Calculate time complexity of modular arithmetic

I wanted to calculate $a \mod n$. What is the time complexity of this? I'm using a Java program? Can anyone provide an explanation of the time complexity for the following calculations? c=a \cdot ...
1answer
35 views

### Why does it take maximum of $n/\log n$ digits to represent the number $2^n - 1$ in base of $n$?

Given the number $n$. Why does it take maximum of $\frac{n}{\log n}$ digits to represent the number $2^n - 1$ in base of $n$?
1answer
58 views

### Number of solutions $x_1x_2\dots x_k = n, x_i, n \in \mathbb{N}$

Here's a question I've been asked: Let $n\in \mathbb{N}$ and let $d_k(n)$ be the number of solutions of $$x_1\dots x_k = n, \hspace{5mm}x_i\in \mathbb{N}$$ I need to show d_k(n) = ...
0answers
367 views

### The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence \$T(m,n) = T(n, m ...
2answers
231 views

### An interesting way of producing positive integers

If we define $$\cal N _1 := \{ 1\}$$ and by induction $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$ it's easy to prove that, for every \$m ...
2answers
403 views

### Factoring n, where n=pq and p and q are consecutive primes

So in RSA, there is a modulus n which is the product of two primes. My question is regarding when p and q are consecutive primes, what would the time complexity be? So, n=pq and p and q are ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9285392761230469, "perplexity_flag": "head"}