## 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

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? 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...