## Search found 27 matches

- Thu May 27, 2021 3:26 am
- Forum: News, Suggestions, and FAQ
- Topic: Tag-Based Organisation
- Replies:
**10** - Views:
**1620**

### Re: Tag-Based Organisation

It works again today. Thank you euler!

- Wed May 26, 2021 12:16 pm
- Forum: News, Suggestions, and FAQ
- Topic: Tag-Based Organisation
- Replies:
**10** - Views:
**1620**

### Re: Tag-Based Organisation

I had enabled Full Tags, and it'd been working for several days. However, the tags disappeared in problem pages today. What's more, when I typed in some frequently used tags like combinatorics or polynomial and clicked search, I didn't get results, but received a message reading "Removed 1 unre...

- Thu Mar 11, 2021 8:51 am
- Forum: Number Theory
- Topic: Calculating modular inverses of p mod $2^p$
- Replies:
**2** - Views:
**1019**

### Calculating modular inverses of p mod $2^p$

Let p an odd prime . We want to calculate $I(p)=p^{-1}\mod 2^p$. If we use EXGCD, it takes $O(\log_22^p)=O(p)$ time, which is not efficient enough. Some small values are 3, 13, 55, 931, 3781, 61681, 248347, 4011943, 259179061...... It seems that $I(p)$ is slightly smaller than $2^{p-1}$, but I didn'...

- Fri Feb 26, 2021 3:43 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 688
- Replies:
**9** - Views:
**4103**

### Re: Problem 688

Hmm...Seems that I'm stuck. I tried sending PM to several administrators, but with no replies for over three months. So could someone help confirm the following results: S(10^6)=***xxxxxxx*** S(10^8)=***xxxxxxxxxxx*** S(10^10)=***xxxxxxxxxxxxxxx*** S(10^12)=***xxxxxxxxxxxxxxxxxxx*** EDIT digits remo...

- Thu Jan 21, 2021 9:52 am
- Forum: Discrete Mathematics
- Topic: Counting constrained squarefree numbers
- Replies:
**4** - Views:
**2058**

### Re: Counting constrained squarefree numbers

It seems that the formula above only holds when d is prime. For example, take d=6 and n=100, the formula yields $S_6(100)=11-2=9$, but actually $S_6(100)=5$. In fact, for squarefree $d=p_1 p_2$, the formula should be $S_{p_1 p_2}(n)=S(\lfloor\frac{n}{p_1 p_2}\rfloor)-S_{p_1}(\lfloor\frac{n}{p_1 p_2}...

- Thu Jan 21, 2021 1:12 am
- Forum: Discrete Mathematics
- Topic: Counting constrained squarefree numbers
- Replies:
**4** - Views:
**2058**

### Counting constrained squarefree numbers

As is known to all, the numbers of squarefree numbers below N can be computed in $O(\sqrt{N})$ time. Now we consider numbers which are both squarefree and NOT divisible by 3 and 5. For instance, there are 20 these numbers below 50, namely 1,2,7,11,13,14,17,19,22,23,26,29,31,34,37,38,41,43,46,47. So ...

- Sat Jan 02, 2021 9:58 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 170
- Replies:
**5** - Views:
**3246**

### Re: Problem 170

Solved the problem, and the answer to leading zeroes appears to be No.

- Sat Jan 02, 2021 4:23 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 170
- Replies:
**5** - Views:
**3246**

### Re: Problem 170

78*12645=986310

78*093=7254

So is 9863107254 a valid answer?

78*093=7254

So is 9863107254 a valid answer?

- Fri Jan 01, 2021 7:38 am
- Forum: Discrete Mathematics
- Topic: How to list all powerful numbers below N in $O(\sqrt{N})$time?
- Replies:
**1** - Views:
**557**

### How to list all powerful numbers below N in $O(\sqrt{N})$time?

Powerful numbers: A positive integer n is powerful if $p^2$ is a divisor of n for every prime factor p in n. From OEIS we know that the number of powerful numbers below N is about $2.1732\sqrt{N}=O(\sqrt{N})$ In fact I do have an algorithm to do so, but some technical issue beats me. The outline of ...

- Sun Dec 27, 2020 1:57 am
- Forum: Discrete Mathematics
- Topic: How to compute a two-variable recurrence function C(n,n) in O(n) time?
- Replies:
**2** - Views:
**634**

### How to compute a two-variable recurrence function C(n,n) in O(n) time?

Suppose we have a two-variable recurrence relation: $C(n,k)=C(n-1,k)+C(n,k-1)$ where boundary values such as $C(n,0)$ and $C(0,k)$ are given. Our target is to find $C(n,n)$. A simple DP algorithm could solve it, but in $O(n^2)$ time, which is not capable of large values of n ($10^7$ or higher). So i...

- Sat Sep 12, 2020 9:03 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 641
- Replies:
**6** - Views:
**4332**

### Re: Problem 641

I got 69 for n=$10^8$, but the answer for $10^{36}$ was rejected. Can I PM someone for some higher results?

- Fri Sep 11, 2020 5:00 am
- Forum: Number Theory
- Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
- Replies:
**10** - Views:
**3488**

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

My algorithm for {1,1,1,...,1} takes roughly O(N). By saying "efficient" here I mean to enumerate numbers of that form without brute force. In other words, an $O(\sqrt[\min(L)]N)$ implementation is efficient enough for me. (Of course, your $O(\sqrt[\max(L)]N)$ approach is much better)

- Sat Sep 05, 2020 3:59 am
- Forum: Number Theory
- Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
- Replies:
**10** - Views:
**3488**

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Got it, but can this implementation compute C(L,N) efficiently? For example, for the case C({5,5,3},$10^{18}$), we need an $O(N^{1/3})$ approach, and for the case C({7,7,5},$10^{30}$),we need an $O(N^{1/5})$ approach.

- Fri Sep 04, 2020 1:16 pm
- Forum: Number Theory
- Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
- Replies:
**10** - Views:
**3488**

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Sorry, I don't fully understand your method. Is your $f(k)$, $g(\lfloor \dfrac n k \rfloor )$ equivalent to C(..., k) and C(..., $\lfloor \dfrac n k \rfloor$) as I described above?

- Fri Sep 04, 2020 4:16 am
- Forum: Number Theory
- Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
- Replies:
**10** - Views:
**3488**

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Thanks for your advice, but how may Dirichlet convolution work in this problem? I'm still new to that concept and its applications.

- Thu Sep 03, 2020 2:13 pm
- Forum: Number Theory
- Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
- Replies:
**10** - Views:
**3488**

### How to enumerate/count the numbers of a particular form below N in an efficient way?

For a sorted array of integers L={$a_1,a_2,...,a_k$}(Eg. L=[3,3,2,2,1]), consider numbers n which can be factored in the form: $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, where $p_1, p_2,..., p_k$ are distinct primes . Let E(L, N) be the enumerating function of all numbers n, not exceeding N, which has the ...

- Mon Aug 31, 2020 12:12 pm
- Forum: Number
- Topic: Identity involving $\sigma(i·j)$
- Replies:
**3** - Views:
**1560**

### Re: Identity involving $\sigma(i·j)$

I found the formula on wolframalpha and solved problem 439 on yesterday evening. Thank you all the same.

- Sat Aug 29, 2020 2:23 am
- Forum: Number
- Topic: Identity involving $\sigma(i·j)$
- Replies:
**3** - Views:
**1560**

### Identity involving $\sigma(i·j)$

As far as I know, there is an identity involving d(i·j), where d(n) denotes the number of divisors of n: $d(i·j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ where [...]=1 if the condition holds, otherwise 0. However, when I was looking for similar identities involving $\sigma(i·j)$ in the form of $\sigma(i·j)...

- Tue Aug 25, 2020 6:11 am
- Forum: Clarifications on Project Euler Problems
- Topic: Problem 272
- Replies:
**15** - Views:
**12391**

### Re: Problem 272

I think I'm on the (seemingly)correct way, but the answer was wrong, even not the same with the "correct wrong" answer. Could you please check: Is the smallest number satisfying C(n)=242 <snipped>? And is the smallest number satisfying C(n)=242 and not divisible by 9 <snipped>? Edit: Solve...

- Fri Aug 21, 2020 1:28 pm
- Forum: Number
- Topic: Unit cube roots in number theory
- Replies:
**2** - Views:
**1754**

### Unit cube roots in number theory

I was trying to solve some particular PE problem these days. It is easy to verify that for any prime power p^k(except 2), there exist two solutions to the equation x^2=1(mod p^k), namely 1 and p^k-1. However, when dealing with the equation x^3=1(mod p^k), the result appeared to differ. For some prim...