elementary-number-theory

[surreal shuttle]

divisble by 2

[sacred junco]

@surreal shuttle
Let's suppose we have a nontrivial relation a^r = 1 (mod n)

Do you understand this?

If not, then rip

[surreal shuttle]

Yes

[sacred junco]

(Ofc asking 'r even' was a joke)

So ye

Now r = 2^k m

You know r is even, right

[surreal shuttle]

yes

[sacred junco]

So you know there is such k for that

Then the question is, what k is it?

Right

[surreal shuttle]

Sure

[sacred junco]

It is about finding maximal k

You can divide r by 2 again and again right? @surreal shuttle

[surreal shuttle]

Yes

[sacred junco]

So, you divide it by 2 until you cannot.

When is it that you should stop dividing by 2?

[surreal shuttle]

Until you can't anymore?

What

until it's odd

?

[sacred junco]

Yup!

Sooooo

You get r / 2^k being odd

[surreal shuttle]

Yes

[sacred junco]

m = r / 2^k

You get this?

[surreal shuttle]

Yeah

[sacred junco]

r = 2^k * m

So what was the pic

t!pic

Write r = 2^k m, with k >= 1, m odd

So now now

Do you get this

[surreal shuttle]

By this you mean...?

Everything or something in particular

[sacred junco]

Write r = 2^k m, with k >= 1, m odd

This

[surreal shuttle]

Yeah

[sacred junco]

So you get how to get the k - you should divide by 2 till odd number to find it.
It is a common pattern btw.
So..

https://cdn.discordapp.com/attachments/418981682117345288/552389698572517398/unknown.png

Next part about b_i, you should understand.

Right?

[surreal shuttle]

Yes

[sacred junco]

Now the important part

You have b_0, b_1, ...

And you have b_k = 1 (mod n).

So there should be the maximal number

Such that

b_l is not 1 (mod n). Right?

[surreal shuttle]

Yeah

[sacred junco]

Yup.

Then of course, l < k

Ye?

[surreal shuttle]

yes

[sacred junco]

And it should be b_(l+1) = 1 (mod n)

[surreal shuttle]

yes

[sacred junco]

So yeah, you get most part of it. right?

All clear, or is there something which is hazy?

[surreal shuttle]

Yeah I get it now thanks

[sacred junco]

👍

(Tbh now I don't know where you got trapped)

(Maybe you don't know why you don't get it before now?)

[pulsar yarrow]

How would I show that F(x,y) = (2y, 3x) is injective or not?

[quick furnace]

by checking whether or not it meets the definition of injectivity, it seems

[pulsar yarrow]

I get to (2y, 3x) = (2y', 3x') but then I don't know what to do after that

[quick furnace]

well

do you know what it means for two ordered pairs to be equal

[pulsar yarrow]

Y and X is equal?

[quick furnace]

in your case, 2y = 2y' and 3x = 3x'.

[pulsar yarrow]

oh okay I see

[fast monolith]

@jolly comet So yeah the competition ended and now i'm open to every solution you can give me :D

[jolly comet]

oh that thing

remind me of the problem again

[fast monolith]

In the decimal representation of 2sqrt = 1.4142... Isabelle finds a sequence of k consecutive zeros, where k is a positive integer. Proof: The first zero of this sequence is at the k-th position after the decimal point at the earliest. Copy past 100

[jolly comet]

if there are k zeroes in a row in they cannot occur too early

okay yeah so here's my idea

there's this theorem which basically says that if a number is "freakishly well" approximated by rationals then it's transcendental

and a freakishly good approximation is one which is a lot closer than you have any reason to expect from the size of the denominator

you can look up the details if you care but you don't need it for the proof i have in mind, it's just a good fact about transcendentals to know when it comes to number theory

we only need to think about quadratic irrationals (which sqrt(2) is because it's a root of the quadratic polynomial x^2 - 2) and those happen to be the weakest of the bunch

[fast monolith]

ok so you don't have the solution.. but this is also interesting

[jolly comet]

i have all the pieces to write down a solution but i didn't do it because i'm not gonna do your contest lol

a rational p/q is a good approximation to a real x if |x - p/q| is minimal among all rationals with denominator <= q

the theorem about "freaksihly good" approximations to algebraic numbers is due to liouville and it says that if x is algebraic of degree n (i.e. if it's the root of a degree n polynomial) then there eixts a c dependent only on x such that |x - p/q| > c/q^n for all rationals p/q

in the case of quadratic irrationals like sqrt(2) it means you couldn't expect to get any better than quadratically close to it

now it's also, separately, known that the best rational approximations come from truncating the continued fraction expansion of a number

the continued fraction for sqrt(2) is 1 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + 1/...)))))

$\sqrt2=1+\frac1{2+\frac1{2+\frac1{...}}}$

[sterile pumice]

tubular:

[jolly comet]

initially 1 but then 2s forever

so, with regards to this problem specifically, you probably don't even need toworry about the liouville result because that requires finding and proving a c which is hella spicy

[pulsar yarrow]

Is F(x,y) -> F(y,y) surjective? I would assume so from common sense as it is possible to make any y if x = y but how would I go about proving it?

[jolly comet]

@fast monolith you know that k zeroes showing up at position p means that $\sqrt2=\frac a{10^{p-1}}+\epsilon$ for $\epsilon<\frac1{10^{k+p-1}}$

[sterile pumice]

tubular:

[jolly comet]

where a is some positive integer which is going to be the first digits of sqrt2

[fast monolith]

sry if i don't answer I had no time rn

tomrrow

maybe

what was that grammer tho

[jolly comet]

so my first strat would be to set p=k and then find the best approximation (from the continued fraction) whose denominator is less than 10^{2k-1} or maybe 10^{k-1}

and then compare that to a/10^{k-1} and presumably learn a contradiction from the fact that the a/10^{k-1} shouldn't be better than the continued fraction result but is extremely good

[sterile pumice]

tet:

[sacred junco]

<@&286206848099549185>? common modulos don't seem to work very well

oops not a help channel, sorry for the ping i guess

[pulsar yarrow]

looking for help on how to solve 5x + 9 = 10 mod 77; a lot of the tutorials i've watched dno't have the _+9

[static sparrow]

something+9=10 mod 77 is the same as something=1 mod 77

[pulsar yarrow]

how does that work

[static sparrow]

$a=b\mod c\iff a-b=0\mod c$

[sterile pumice]

Tuong:

[static sparrow]

if a=b mod c then there exists k in Z such that a=b+kc, so a-b=kc.
k is in Z so a-b=0 mod c

if a-b=0 mod c, then there exists k in Z such that a-b=kc, so a=b+kc.
k is in Z so a=b mod c

[pulsar yarrow]

right

can a be like somethingx

so 5x = 1mod77

[static sparrow]

Yeah

[pulsar yarrow]

5x -1 = k77?

wait that doens't make sense

[static sparrow]

5x=1 mod 77 means there exists k in Z such that 5x=1+77k
5x-1=0 mod 77 means there exists k in Z such that 5x-1=77k

it's really the same

you can add stuff like you want

[pulsar yarrow]

but regardless how do I find x

[static sparrow]

,calc 31*5-1

[sterile pumice]

Result:

154

[static sparrow]

,calc 154/77

[sterile pumice]

Result:

2

[static sparrow]

So, 31 is a solution

[pulsar yarrow]

how did you find that

[static sparrow]

I did 77*2, it ends with a 4, so it's a multiple of 5 minus 1

5×31-1=2×77

If you can't find an easy solution, there's an algorithm to compute one, but I don't remember it

[pulsar yarrow]

wait so

you moved the 1 over

but why did you * 2

and after that what happens

[static sparrow]

77×2 ends with a 4

77×2+1 end with a 5, it's a multiple of 5

then (77×2+1)/5=31

[pulsar yarrow]

why you multipled the 77 by 2 you didn't have to multiply the side of the 5 as well?

[static sparrow]

I'm not working with the equation, I'm designing a solution from scratch

when you've got equations like this, there's often an "easy" solution with which you obtain all the solutions

here, 31 is an "easy" solution

and when you can't find one of those "easy" solutions, there's an algorithm to obtain one, but I can't remember it right now so you'll have to look for it in your notes

[pulsar yarrow]

but the easy solution should still fit in the equation right

so if its 5x = 1mod77

if x = 31

[static sparrow]

It had something to with Bézout iirc

[pulsar yarrow]

does 155= 1mod77

[static sparrow]

yes

155=154+1
154=2×77

[pulsar yarrow]

ugh mod is hard to wrap my head around

[static sparrow]

a=b mod c means there exists a k in Z such that a=b+kc

it's an existence thing

[pulsar yarrow]

okay

but what happens if i need to solve 2 equations

so like

x = 2mod7 and x = 3 mod11

i assume i cant do it like linear equtaions

[static sparrow]

To solve tbese, you use theorems you've learned in class

7 and 11 are coprime so iirc there's something special about that situation

I dont' remember it exactly though

I'll go to sleep now, good luck with your exercise!

[pulsar yarrow]

okay thanks!

[stuck lintel]

since 7 and 11 are coprime you can apply the chinese remainder theorem

which states that if 11z = 2 mod 7 and 7y = 3 mod 11, then x = 11z + 7y mod 77

,tex more generally if you have \$x \equiv a_1 \pmod{m_1}$
and
$x\equiv a_2\pmod{m_2}$ and $(m_1, m_2) = 1$\ then solve the equations $z_1m_1 \equiv a_2 \pmod{m_2}$ and $z_2m_2\equiv a_1 \pmod{m_1}$ \ and $x \equiv z_1m_1 + z_2m_2 \pmod{m_1m_2}$

[sterile pumice]

Plum:

[stuck lintel]

it gets more complicated if you have 3 or more relations at once

[pulsar yarrow]

yup jus tfound it

seems fairly straightforward

unlike when there's 2 variables

im not sure what to do when its x and y

so like x + y = 33 mod 77, and x-y =10 mod77

i tried combining it to get 2x = 43mod77 but then im not sure what else

[stuck lintel]

ya that works

[pulsar yarrow]

i dont know where to go from tehre

i'm trying to isolate x right?

[stuck lintel]

2x ≡ 43 mod 77 -> 2x ≡ 120 mod 77 -> x ≡ 60 mod 77

[pulsar yarrow]

how did you get 120?

[stuck lintel]

add 77

remember what he said about if a = b mod m and c = d mod m, then a + c = b + d mod m

and since 77 = 0 mod 77, then a + 77 = a mod 77

[pulsar yarrow]

okay

so are you able to divide across congruences?

[stuck lintel]

yeah you can divide as long as it’s coprime to the modulus

[pulsar yarrow]

How would I remove the 5 from 5x ≡ 1 mod 77
What values am I alloewd to mulitply both sides by

[sacred junco]

5x = 1 mod 77
5x = 155 mod 77
x = 31 mod 77

same trick

[pulsar yarrow]

oh I completely forgot about that

thanks!

[sacred junco]

np

[pulsar yarrow]

why can you just add 77 to the right again

oh cause modding gives the same remainder?

[sacred junco]

because it's the same thing as adding 0 to both sides

yeah

[pulsar yarrow]

and I can divide both sides by any number as well as multiply?

[sacred junco]

multiply yes, divide not so much

you can only divide by some number if that number is coprime to the modulus, 77 in this case

[pulsar yarrow]

okay and how about adding and subtracting to both sides

[sacred junco]

allowed

[pulsar yarrow]

okay and so for congruencies the mod isn't part of the particular varibale, but part of the entire side right so

[sacred junco]

what do you mean

[pulsar yarrow]

its not like ( ) = ( (xmodx) ) but rather (LS) = (RS) modx

or is it just a property of the congruency

so if like x = 1mod6, and I wanted to add some number, it'd be x + y = 1 + y mod 6 instead of x + y = 1mod6 + y

cause 1mod6 can just be evaluated?

[sacred junco]

the first thing you said

in general, if a = b mod n
c = d mod n

then a + c = b+d mod n

and also ac = bd mod n

[pulsar yarrow]

If I'm just adding a number how do those apply

[sacred junco]

then you set one of the pairs equal to each other

so c=d

go back to your congruence, 5x = 1 mod 77

since 0 = 154 mod 77, we can add this congruence to our first one

5x + 0 = 1 + 154 mod 77

[pulsar yarrow]

Ohhhh

Is that the case for multiplying both sides as well

[sacred junco]

yeah

[pulsar yarrow]

I see okay that makes sense

thanks

[sacred junco]

np

[sterile nymph]

how would you do this problem?

[swift shard]

Gotta take it mod 10

[stuck lintel]

try to find the units digit of each of those terms individually by noticing a pattern in their units digit

how would you find the last three digits of that sum tho hmmmmmm

[swift shard]

Add the digits, take it mod 10

You've only got to multiply until you see a repeat
2¹ = 2
2² = 4
2³ = 8
2⁴ = 16
2⁵ = 32
And there it is, 2¹ ≡ 2⁵ ≡ 2^(4n + 1)

Namely, 2^(2017) = 2^(4×504 + 1) ≡ 2

[vernal ravine]

I think I proved the Collatz Conjecture for all even n but my proof is extremely dodgy

[jolly comet]

uh

using the word "even" suggests you have no idea what you're talking about

because an answer for all even n would very easily imply an answer for all n

[vernal ravine]

I mean for all n ≡ 0 mod 2

[jolly comet]

i know exactly what you mean

every odd n is the result of one collatz step from the even number 2n

[vernal ravine]

Oh you're right

[jolly comet]

it's my professional opinion there's no way you can have a legitimate proof of what you claim to know if that escaped you

[swift shard]

Well there, you've proven the collatz conjecture! Good job

[vernal ravine]

I never said I had a legitimate proof

But essentially if it can be shown that every n can be written in the form (n*(3^k)+2*m)/2^l such that the result forms an integer, then the Collatz Conjecture is true for all n

Pardon the horrid handwriting

Never mind I'm an idiot I'll just leave

[jolly comet]

the collatz conjecture is that every integer transforms into 1 after a finite number of collatz steps

[vernal ravine]

Yeah, I showed in the base case that the integer 4 transforms into 1

And then just used a piss-poor version of induction from there

Obviously it has some holes in it but I think I'm making progress

[jolly comet]

(1) this is not how you use induction with multiple variables; your setup for incrementing the variables would only imply anything for the cases where k = m = l, and it is very much not the case that an integer can be written in that form for k = m = l
(2) it's not clear what is being proven in your inductive case or how you prove it
(3) i think you are using the letter n in multiple contexts and pretending like they're the same (or accidentally confusing them) when they're not

it sounds like you are searching for a form such that every positive integer can be written in that form, and applying a collatz step reduces that form in a way that you can handle by induction

[vernal ravine]

Yeah that's what I'm trying to do

[jolly comet]

this is a plausible strategy, if such a form exists

[vernal ravine]

I apologize for my incompetence, I'm only in vector calculus right now and have yet to take discrete math

[jolly comet]

however, there is no heuristic evidence that such a form does exist

i would suggest you learn a little more about induction to see how it applies in the case where there are multiple variables

the one-variable case is a lot simpler than the general case and it requires a lot of care to make sure you're saying what you want to say

[wind falcon]

Is what I'm trying to prove even true?

[sturdy dirge]

Of course.

[stuck lintel]

what does r_1, r_2, ... stand for?

[sturdy dirge]

It's probably a proof for:

$\forall (a, n)\in\mathbb{N}^2, n>1,a\wedge n=1, a^{\phi(n)}\equiv1\pmod{n}$.

[quick furnace]

what is \wedge

gcd?

[static sparrow]

Yes, it's some infix notation for gcd

[sturdy dirge]

Yes.

[stuck lintel]

Right but what are r_n supposed to represent

[sturdy dirge]

Maybe:

$r_i\equiv a^i\pmod{n}$.

[brittle patrol]

They're prolly just the $\varphi(n)$ numbers smaller than $n$ and relatively prime to it

[sterile pumice]

Gonzo17:

[noble jay]

@static sparrow only for us french people

i've never seen anyone else use it or even recognize it when i use it

[last zealot]

I have a number theory question up at #help-1

[languid fog]

Someone PLEASE HELP :((

I've been struggling with 8(b)

Yeah, but how do I get the actual factors

How does this tell me anything about the options tho?

2,2

1 and 4

So I have to find solutions for a^2+5b^2=2 and such?

Yeah, I see that. But how do I show that

Oh shit I get it

Thanks man

[tender copper]

question

what is the closest thing to a method of turning sequences of numbers into functions there is?

[silver solar]

Linear interpolation I suppose

[tender copper]

isnt there a simpler way?

[sacred junco]

That's the simplest form of regression analysis, which is by definition the only way to accomplish such a task.

[tender copper]

what if the function is know was a polynomial of degree n and you just have to find it

without using roots

[sacred junco]

That's not how polynomials work

They always have roots

[tender copper]

well if roots are not given

[sacred junco]

Lagrange interpolation?

[tender copper]

like for example a function of degree 2 with 4 points that are consecutive

[sacred junco]

Example

[tender copper]

(1,2) (2,9) (3,22) (4,41) (5,66) (6,97)

[sacred junco]

Yeah just do regression

[tender copper]

hmm

so there isnt any other way yet?

[sacred junco]

If you know exactly that it is polynomial, use Lagrange interpolation

But it is sensitive to small changes in data
so never do this if the data are not exact

[tender copper]

i think i have a simpler method

9-2 is 7

22-9= 13

13-7=6

which is the last derivative of the function

still working on it

maybe i will have a ready version in a month

[sacred junco]

yes, this also works

if your points are consecutive

this is called newton interpolation

[tender copper]

huh

newton has discovered it all

;-;

sad

so what are the limitations of newton interpolation?

[sacred junco]

No limitation
it allows you to find the unique polynomial which has given values at given points

but this is not always what you want

[tender copper]

how so?

[sacred junco]

if your data is from experiment for example
it can contain errors
and in this case the exact interpolating polynomial may be worse than lower degree regression

,wolf interpolating polynomial [(1,1.03) (2,1.96) (3,3.05) (4,3.98) (5,5.01) (6,6.03) (7,6.95)]

[sterile pumice]

Display results online and refine query

Requested by Xaositect#5991

[tender copper]

i see

[sacred junco]

ok maybe it's not that good of an example
but on the first segment for example it is worse than the straight line

[tender copper]

does it also do exponential + polynomial functions ;-;

[sacred junco]

no

use regression

[tender copper]

eh im just a highschooler i dont think i will be able to understand it fully

[sacred junco]

oh

it's not that hard, but some background knowledge is of course needed

What do you need this for?

[tender copper]

idk

i thought i stumbled on something interesting and new

but turns out newton already did it

[sacred junco]

It's good

[tender copper]

i was just bored in class

[sacred junco]

If you rediscover something that is useful enough to attach someone's name to it

it means that you are good

[tender copper]

well i found a way to use the method with functions that are + exponential

like x^2 + 2^x

and still testing with products but i think i have a clue

well its all relates to pascals triangle

[sacred junco]

with polynomial + a^n the differences will eventually multiply by (a-1)?

that's nice to play with these things

[tender copper]

multiply by a

because its like deriving the function infinite times

[sacred junco]

oh, yeah

[tender copper]

the polynomial becomes 0 but the exponential part stays the same

[sacred junco]

ah

yes

maybe try to read the book "Concrete mathematics" when you are done with your tests

the beginning should be accessible

[tender copper]

huh

i will try to check it out on my spring break

[noble elm]

so, im sorta stuck here. If $\frac{3^k+1}{2}$ is prime, how do we know that $k$ must be a power of two?

[sterile pumice]

em:

[noble elm]

I got as far as seeing that since $3^k = 2*p - 1$ for some prime $p$, that $3^k \equiv -1 \mod{p}$

[sterile pumice]

em:

[noble elm]

but idek if that's the right direction i wanna be headed

in the congruence or to the original form?

[hearty timber]

any of them

try a couple cases

k = 1, k = 3

see what happens

generalize

[noble elm]

1 is a power of two u noob :V

ily jaco

ohhh I think I see

So if k is not a power of two, $k=2^j * m$ for some odd $m$. Then $3^k+1 = (3^{2^j}))^m + 1 = (3^{2^j}))^m - (-1)^m$ since $m$ odd. This is divisible by $3^{2j}+1$

[sterile pumice]

em:

[noble elm]

so it isnt prime :V

thanks dad

?

oh we div by 2

fuck

hhh k

oh, 3^k+1 is always 0 or 2 mod 4 innit

derp

oof

oh wait lol that doesnt matter at all

adfklasdfkl

bc 3^2^n + 1 divided by 2 is an integer anyway

lmfao

i mean i thought the logic held for a second there lmfao

if we divved 3^k+1 by not 2 it would matter lmao

proof by contradiction is a lie

:V

yeah I somehow never quite realized (or at least internalized) that not a power of two implies a power of two times some odd factor

huh, weird

ive taken a few semesters of combinatorics based classes and maybe just never really considered it

But then again I'm a constructivist

[tribal abyss]

Can you take a number in a group, let's say in the rationals, and take it to the power of another number in that same group, and get a number in the group above as a solution.
So: a^b = x
Where: a,b = rational, x = irrational.
Will it just be that you can only get number from that group and nothing above no matter the operation?

What about something like e^π? Will it give another transcendental number?

[stuck lintel]

wdym?

are you saying if its possible for x to be irrational or for x to be rational

because x can either be rational, i.e. 1^1, or irrational, i.e. 2^(1/2)

also e^pi was proven to be transcendental, however pi^e, e + pi, and e*pi arent proven

[swift shard]

Doesn't make sense in the context of a group, since gⁿ is short form for gggg...

So n is always an integer

[last zealot]

I was trying to prove this

and realised that this isn't true since if m=9, n=2 then 9|2 then it doesn't hold

Am I right?

[exotic raptor]

for m=9

9 has one prime divisor (3)

2¹=2

n can be either 0 or 1

as 0*(-1)=1*0=0 ≡ 0 (mod 9)

that's 2 total so it does work for m=9

[last zealot]

Ohh thanks for that

[trim gull]

Can someone tell me how you go from the term 3^(n+1) to 3^n * 3?

[stuck lintel]

3^n * 3 = 3^(n+1)

you add exponents

[trim gull]

What rule is used here @stuck lintel ?

Nevermind . I got it! thanks

[drifting inlet]

p+q=1 and 0<p<1 and 0<q<1

is there a way of finding the max value of pq

[gilded tinsel]

q=1-p

use calc

but there is a more elegant argument

[grizzled stump]

A rigorous solution, but overkilling it would be to use Lagrange mutlipliers

[gilded tinsel]

anyway

this isnt number theory

[grizzled stump]

Haha certainly yes

[drifting inlet]

sorry

where shall i post it

[grizzled stump]

Analysis or calc

[gilded tinsel]

or #❓how-to-get-help

if you dont know which topic it resides in

[stuck lintel]

By AM-GM, (p+q)/2 >= sqrt(pq), so the maximum value of pq is taken when (p+q)/2 = sqrt(pq). Plug in p+q=1.
1/2 = sqrt(pq)
pq = 1/4

@drifting inlet

Additionally, you could also use basic algebra. q=1-p
p(1-p) = -p^2 + p.
The vertex of a parabola is at the x value -b/2a.
p = -1/-2 = 1/2
-p^2 + p = -1/4 + 1/2 = 1/4

[sacred junco]

parabola

[stuck lintel]

Fuk

[sacred junco]

lol

[exotic raptor]

[devout trail]

Can someone please explain to me the conclusion in the last sentence of the solution?

[drifting inlet]

Thanks @stuck lintel

[low jolt]

Then it can be seen EASILY that $ n(n+1) $ is congruent to 0,1,2 modulo 5. Is this based on observation or can we mathematically prove that $ n(n+1) $ is indeed congruent to 0,1,2 modulo 5?

[sterile pumice]

Rumoden:

[exotic raptor]

you can just check from 0 to 4 and the rest follows

not sure if there's a faster way

[low jolt]

🌬

ok thennn

thanks!

[low jolt]

howw

[stuck lintel]

Context?

[low jolt]

mod 11

[quick furnace]

$12 \equiv_{11} 1$

[sterile pumice]

Ann:

[quick furnace]

$20 \equiv_{11} 9$

[sterile pumice]

Ann:

[low jolt]

ah i see lol thanks very much!

[hollow lark]

hello, someone showed me this but i don’t know what is happening between the 4th and the 5th line. can someone explain it to me ? thank you !

https://imgur.com/gallery/8LAhiUK

[static sparrow]

they moved the index

Oops wrong line

[hollow lark]

i mean the line under, when it starts by C^n _n

[static sparrow]

they isolated the first and last terms

[hollow lark]

alright i’m an idiot

thank you !!

[static sparrow]

You're welcome

[raw cypress]

Hey guys! So I’m trying to learn a quick way on how to calculate the politeness of a number and I’ve been looking up some explanations and they’re are very vague and sometimes not true.

For example the wiki explanation

[exotic raptor]

uh

count the odd factors apparently

[raw cypress]

hmm the formula work for an integer like 9?

[exotic raptor]

9 has 2 odd factors and a politeness of 2

||except 1||

[raw cypress]

When would you refer to the formula?

18

90

[exotic raptor]

Well it'll work for any

[raw cypress]

90 has 3odd factors however it’s actually 5

But then the formula is true

18 has 2 odd factors which is true.

But the formula is false

[exotic raptor]

3, 5, 9, 15, 45

[raw cypress]

Ohh

I have to get all the odd factors? I just did a tree of 10 and 9

[sick ravine]

Hi, I need to calculate the gcd of some very large numbers, using the euclidean algorithm isn't an option here. Could someone suggest some techniques I could try to get there? For instance, I know that 2 is factor of the gcd, I also know that 2 is in fact the gcd (I used a calculator). I thought of expressing 2 as a sum of the numbers, but that would require using the euclidean algorithm. Are there any general methods I could try?

[crystal pond]

Prime factorization..?

[sick ravine]

I would go about that but they are expressed as power of prime +/- 1. Even otherwise they are very large, this would take a long time manually

[silver solar]

How big are the numbers?

[sick ravine]

approx 50 ^ 500

[crystal pond]

hmm ok no prime factorization

[silver solar]

Maybe you could try doing something with the fact that they're almost-prime powers

[sick ravine]

They aren't intractable, I can write a python program to compute the answer. Just wouldn't work manually

@silver solar, could you elaborate a little bit, I'm not sure how I would do that

[gilded tinsel]

what are your two numbers exactly?

perhaps they have some special property

[sick ravine]

@gilded tinsel, sorry for the late reply. If possible only give a hint please. Here is the number I need to compute: gcd(x ^ 671 + 1, x ^ 610 - 1) where x = gcd(61 ^ 610 + 1, 61 ^ 671 - 1)

[crystal pond]

The GCD is 2 right

So I’m thinking it has something to do with how one of them is +1 and other one is -1 and 61^671 is simply (61^610)(61^61)

[sick ravine]

x = 2, but I can't prove without using the division algorithm

[crystal pond]

Yeah

Wait is 61 prime

[sick ravine]

yes

[crystal pond]

Hmm okay I need to think about it some more haha but I think we’re quite close to the crux

[sick ravine]

The results I've already got are that 2 | x and x | 61 ^ 61 + 1

I don't think the second one is useful however

[gilded tinsel]

okay i think i proved x is 2

x should divide the sum of two numbers in the gcd

$x|61^{610}(61^{61}-1)$

[sterile pumice]

rockpaperscissors:

[gilded tinsel]

for simplicity ill call 61^610 * (61^61-1)=y

suppose a prime p divided y

p then is either 61 or p|61^61-1

that is $61^{61} \equiv 1 \pmod p$

[sterile pumice]

rockpaperscissors:

[gilded tinsel]

if p=61 this is false so suppose p does not equal 61 (anyway 61 does not divide any of the numebrs in x)

the order of 61 in Z/pZ is then a divisor of 61 i.e either 1 or 61

[sick ravine]

Shouldn't the sum of the two numbers be 61^610 + 61^671 = 61^610(6 ^ 61 + 1) (not minus 1)

[gilded tinsel]

shit

okay i think i can fix this

[sacred junco]

shit

[crystal pond]

It was looking really good!

[sick ravine]

The way your proof is proceeding we can try to eliminate 122 as a possibility

We'll also have to eliminate 2

[gilded tinsel]

$61^{61} \equiv -1 \pmod p$

[sterile pumice]

rockpaperscissors:

[low jolt]

I don't understand the $2^n + 6 \cdot 9^n ≡ 7 \cdot 9^n$.

[sterile pumice]

Rumoden:

[sacred junco]

since 9^n = 2^n mod 7

what is (1)2^n + (6)2^n

[low jolt]

hold on

uh can you help me out here

[sick ravine]

The author adds 6 * 9 ^ n on both sides of the congruence

RHS was already 9 ^ n

So we get 1 * 9 ^ n + 6 * 9 ^ n = 7 * 9 ^ n

Clearly 7 | 7 * 9 ^ n

Therefore, 2 ^ n + 6 * 9 ^ n = 0 mod 7

[low jolt]

So it's something like $... ≡ 9^n + 6 \cdot 9^n$ so $9^n (7)$

[sterile pumice]

Rumoden:

[sick ravine]

Yeah

[low jolt]

got it thanks.

[sick ravine]

Sure

[crystal pond]

kj wdfjkhds fjkdhs f

@sick ravine I THINJK I GOT IT

wait

maybe

I dunno just try and follow my reasoning and see if it's flawed

So like, we observed that both 61^610+1 and 61^671-1 has a GCD of 2

Now we will prove this is the highest GCD

So we know by the fundemental theorm of arthimetic or whatever

each no. has a unique prime factorization

So if 2 was not the highest GCD

There would be some number greater than 2 that divides both numbers

And that number must be odd, since primes are well odd

So if that numbers divides them

it must also divide the sum rite

so the sum of 61^610+1 and 61^671-1 is like

61^610+61^671

then we factorise

61^610(61^61+1)

ok so we know 61^610 is odd

and 61^61 is even

odd x even is even rite

and we know the prime we're dividing is odd

so we have a case of even/(prime) which is even/odd

That means our result must be even

But the remaining prime factors must be odd

Because odd x odd x odd is odd

I think

Am I right?..

[sick ravine]

Couple of things

[sacred junco]

you still haven't proved that gcd can't be 4,6,8,...

[sick ravine]

Couldn't the gcd be 4

[crystal pond]

oh yeah shit

[sick ravine]

exactly

[crystal pond]

sad

[sacred junco]

hahahahaha

[crystal pond]

k jhdjkhdsjkf

I was so close cries

WAIT

nvm

sigh

[sacred junco]

i was wishing you said "but odd can't divide even"

[crystal pond]

I'm bad :<

[sacred junco]

so you would've had 2 wrong statements instead of 1

lol

[crystal pond]

haha..

[sick ravine]

Does x^n + 1 have factorization formula?

[sacred junco]

only if n is odd

[sick ravine]

okay, make it -1

[sacred junco]

x^n - 1?

this has a nice factorisation

(x-1)(1 + x + x^2 + x^3 + ... + x^(n-1))

[sick ravine]

Sorry, I meant x^n - ( -1 )^n and use the formula you mentioned

[sacred junco]

o

[crystal pond]

ok wait I think I kinda got it

So previously my proof was okay right

It's just that I didn't proof like

the 4, 8, 16 cases

Do I just have to prove that if 61^610+1/2 is odd

then like it's good?

sorry (61^610+1)/2

[sick ravine]

Yes, that would work

This can be shown using euler's theorem

[crystal pond]

Oh owo

[sick ravine]

61 ^ 61 = 61 = 1 mod 10

[crystal pond]

wait so are we done!!!

[sick ravine]

61 ^ 61 + 1 = 2 mod 10

[sacred junco]

lol

[sick ravine]

Yes we now have X, I shall work on computing the final value. Thanks a lot for the help everyone!

[crystal pond]

Oh yaY!!!

I hoped I contributed something owo haha

And I'll go read up on euler's theorem thanks

[sacred junco]

you contributed the fact that all primes other than 2 are odd

[crystal pond]

So I didn't contribute anything

[sacred junco]

lol

[crystal pond]

cries in dismay

[sacred junco]

also

what is phi(10)

,w phi(10)

[sick ravine]

Yep, a very important part of the proof

[sterile pumice]

Display results online and refine query

Requested by Oxide#6480

[sacred junco]

oh ok

then that would work perfectly

[sick ravine]

No @crystal pond proved that x can't have any odd prime factors

[crystal pond]

oh yay so I did something :>

Sometime I like to think I'm good at math even if I know I'm not really

I don't know honestly I kinda wanna be a teacher when I grow uppp

[sick ravine]

I'm pretty sure every mathematician feels that way

[crystal pond]

Yeah I guess so, I just like teaching though, the feeling of seeing a student enlightened is something

not quite describable by words

[sacred junco]

become a buddhist

[crystal pond]

Does that enlighten people

[sacred junco]

lol

actually let me rephrase that

become the buddha

[sick ravine]

I meant, the part about where you said that you felt you aren't good at math

[crystal pond]

I see well

I don't have enough hands sorry :<

[sacred junco]

wot

do you have less than 2 hands

[crystal pond]

Oh shit wait

bhudda is the one with 2 hands

which was the one with many hands

[sacred junco]

lmao

many hindu gods

[crystal pond]

Ah but yeah I don't think anyone would worship me though

Nevermind none of this is number theory

Bogeyman urr I'm glad I contributed something, have a nice day :>

[sick ravine]

Same to you man. Thanks a lot for the help!

*bogeyboy

[sacred junco]

bogeyman

[sick ravine]

@crystal pond , could you explain the last part of your proof again? even/odd = even, but what contradiction did we arrive at? why must (61 ^ 61 + 1)/odd = odd, why can't it be even?

[crystal pond]

okay so the last part of my proof is even/odd = even

and the contridiction is because

when we prime factorize something

the rest of it's factor are all prime numbers greater than 2

which are odd numbers

So we know the result should be odd

Urr how do I say it

Okay lemme try and phrase it better

[sick ravine]

Our aim is to prove that x can't have an odd prime factor, but I don't see how does this contradict that

[crystal pond]

Okay lemme explain the later part

then I'll rephrase the earlier part

the 61^61+1/odd

and wait no it's

61^61+1/2

is odd

[sacred junco]

isn't that assuming what we wanted to prove

[crystal pond]

because then we have shown that 2 is the greatest prime factor

Isn't that proving that 2 is the gpf

Because if it was even

[sacred junco]

okay wait

can you put your proof again

[crystal pond]

bzzzz okie

[sick ravine]

Say, we arrive at the result using the eulers theorem proof since that doesn't depend on Itadaikmasu's proof

we now have 61^61 + 1 / 2 is odd

[crystal pond]

No my proof and that proof

Kinda need each other..?

[sick ravine]

but now x and 61 ^ 61 + 1 / 2 may have a common factor

[crystal pond]

But we're proving that 2 is the GCF

The proof right

61^61+1/2 is odd

it needs the earlier proof first

then it makes sense

[sick ravine]

Nah, theother proof only says that 1 is the highest power of 2 in the prime factorization of 61 ^ 61 + 1

[crystal pond]

because once we know there are no prime factors greater than 2

sorry

no prime factors

greater than 2^n

for some interger n

then we proof that n is 1

First we prove x is 2^n

then we prove n = 1

[sick ravine]

The order you prove it in doesn't really matter, but please do explain how we arrived at x = 2^n for some n, I didn't get the last part in your proof

[crystal pond]

Okay one sec I need to see if my proof is like yeah

oh earlier I made a typo

61^61+1 is even

sigh my own proof confuse me

[sick ravine]

I don't think we arrived at a contradiction

as in x/2 and 61^61 + 1/ 2 may still have an odd common factor

[sacred junco]

i think i came up with a proof that an odd prime cannot divide 61^(610) + 1 and 61^(671) -1

say it is p

then $p | 61^{610} + 1$ and $p | 61^{671} - 1$

[sacred junco]

ofc as ita said, it must also divide their sum

then $p | 61^{610} (61^{61} + 1)$

[sick ravine]

we know p!= 61

[sacred junco]

now since p is prime, either $p | 61^{610}$ or $p | (61^{61} + 1)$

[sacred junco]

consider case 2

$61^{61} \equiv -1 \pmod{p}$

[sacred junco]

raise both sides to the 10th power

[sacred junco]

but that would mean:

[sick ravine]

brilliant! chefs kiss

[sacred junco]

but we assumed that 61^(610) + 1 was divisible by p

so clearly $p \nmid 61^{61} + 1$, what we have left to disprove is that $p | (61^{610})$

[sacred junco]

then multiply by 61^(61) on both sides

[crystal pond]

okay this proof makes more sense thanks :">

@sick ravine Hey curious question but like

what year are you..?

and what course is this

or maybe like how old is a more appropriate question

[sacred junco]

lol

hm, now that's all left to prove is that if $2^k \mid 61^{610} + 1$ and $2^k \mid 61^{671} - 1$, then $k = 1$

[crystal pond]

Was this the one where odd and even came in

Or more modulo owo

[sacred junco]

idk

[crystal pond]

We know there are no primes greater than 2 right?

[sacred junco]

hahahahahahaha

[crystal pond]

Waigt

I mean there are no prime factors

Idek

jkjshdjfkhds

[sacred junco]

yeah

this is so good

[crystal pond]

HAHAHA OK PLS DONT QUOTE ME ON THAT

Well okay so uhhh I think we should divide both numbers by 2

[sacred junco]

and if it is odd

[crystal pond]

if one of them is odd then we know

yeah^

[sacred junco]

how will you divide them

[crystal pond]

I thought we were using eulers theorem or something

[sacred junco]

oh wait i got it

$61^{671} \equiv 1 \equiv 183 \pmod{2}$

[sacred junco]

and ofc, gcd(61, 2) = 1 so we can divide by 61

and note that 183 = 3 * 61

$\frac{61^{671}}{61} \equiv 3 \equiv 1 \pmod{2}$

[sacred junco]

wait a minute

we were supposed to divide by 2 lmao

[crystal pond]

uh yeah..?

I'm sure how to prove this one because like

even/even gives even or odd

I dunno how to prove it's odd

[sick ravine]

Sorry, I'd lost connectivity for a moment there. This proof is great! No odd prime and minimum and greatest power of 2 is 1. Therefore x = 2

[sacred junco]

[crystal pond]

Well okay

[sick ravine]

Once again, thanks guys

[copper dome]

https://www.youtube.com/watch?v=5TkIe60y2GI this is neat

[stuck lintel]

Not really number theory

[sacred junco]

lmao

what a parker square of a video

[copper dome]

what channel should i have put it in @stuck lintel?

[sacred junco]

mathematics

[raw cypress]

Not sure if this is the right channel but would any of you guys happen to know how to approach this problem?

This type of problem has appeared twice in previous math comp test

[crystal pond]

I think the trick is that the expression above is rational

Meaning it's going to be recurring

Most likely

recurring decimals such as 0.9999

can be expressed as infinite sums

i.e. $\sum{1}{\infty}{9/10^n}$

[sterile pumice]

Itadakimasu!:

[crystal pond]

NOPE

thatss jdwhjsh urgh

[raw cypress]

Look at this

they used the fib sequence but why?

[exotic raptor]

$\sum_{n=1}^{\infty}{9/10^n}$

[sterile pumice]

CaptainLightning:

[crystal pond]

oh okay

thanks^

Okay so they look for the

21+3=7

21/3=7*

[exotic raptor]

oh

[crystal pond]

Wait but that doesn't make sense

the 7th term in the fibonacci swq isn't

3

[exotic raptor]

the golden ratio satisfies x²-x-1=0

[crystal pond]

Oh yeah

okay okay I got it

If you do sub 10=x and you do long division

You began to like see the pattern emerging

In case you can't think of fibonacci during the exam

[raw cypress]

ohhh I see it

[sacred junco]

ah yes

x/(x^2 - x - 1) is the generating func of fibonacci

how sly

[astral pike]

So...how about that multiplicative persistence?

[haughty falcon]

well, being an idiot, I implemented a program that checks if a new number can be deduced from 277777788888899 and it's currently running

[sacred junco]

what do you mean by deduced from

[haughty falcon]

however I did the analysis of the computation time, and it's O(n^15), where n is the number of 1s spliced into the permutations of the number

well, you can rearrange the digits and splice in 1s and then test if all factors are less than 10 (more exactly 2, 3 and 7 are enough. 5 is impossible if working with the given number)

if so, then you can just bunch those factors together and have a number with persistence 12

so, I quickly calculated how many numbers I have to check when I have spliced in n 1s, and it's about ((15+n)^15)/(10^6), using sterling's formula for factorial and a few other simplifications (and assuming I did nothing wrong)

here's the crappy code
feel free to do whatever you want with it

just to be sure. this is how you compile it:
gcc persi.c -o persi.exe -lgmp
I guess trying all numbers of the form (2^a)*(3^b)*(7^c) diagonalized by a+b+c=n for their persistence is probably more efficient and could even benefit from some dynamic programming (though I guess the usual recursive approach won't be much slower)
edit: quickly estimated the operations for the second algorithm and it's something like 5*n^2, with n still being the number of digits more than the 15 we already know

[raw cypress]

Any approaches?

[haughty falcon]

so were talking sum((3^n)/n!)?
that would be e^3, going by sum((x^n)/n!)=e^x

but is there a base 10 algorithm for single digits of e^x?

[raw cypress]

yeah that is the approach the paper had. thanks

[wind falcon]

I need a little help in #help-3 if anyone minds

[low jolt]

Hello. I'm currently trying to study number theory. I think it's a fascinating field of study. However, whenever I read the articles, such as proving that gcd(x,y) = gcd (x+y,y) or something else like that I can't follow up. I also have trouble trying to answer the questions since I often don't see how to solve it. Has anyone had similar problems? Mind sharing?

[sacred junco]

@low jolt see: euclid's algorithm

oh your question was more general than i initially thought it to be

[low jolt]

yeah :^(

i mean i tried doing practice problems

but i rarely finish a problem because i get stuck

[sacred junco]

just like
don't give up so quickly

and try small cases, if that's possible

[noble jay]

@low jolt when you get stuck stop working on it and then go back to it the day after

[low jolt]

ay thanks both of ya.

[sacred junco]

@low jolt u could check out some YouTube channels

[grim thicket]

Would the linear congruence x = 2 mod 3 have infinite answers?

[swift shard]

Yes

Well,
x ≡ 2 (mod 3)
Does

[grim thicket]

Im kind of confused because I'm asked to find all the answers to the congruence 16x congruence 32 (mod 48) and i simplified it down to x congruence 2 (mod 3), how would I list all the answers?

[abstract sinew]

to start, can you list some answers?

[grim thicket]

I've gotten 2,5,8,11,14,...

adding 3 each time

[swift shard]

Easy, the answers are x = 3k + 2, where k is an integer

[abstract sinew]

is that all of them?

[grim thicket]

Not all of them, I read that a congruence b (mod m) and if gcd(a,m) = d and d|b then there are d number of answers but if I write x = 3k+2 there would be an infinite amount of answers

[abstract sinew]

there are d answers mod m

[grim thicket]

in this case d mod m would be 16 right?

[abstract sinew]

don't look at d mod m

but yes, d is 16 in this case

[grim thicket]

I've written out 16 answers starting from 2 all the way to 47 but 50 seems to also be an answer

[abstract sinew]

what is 50 mod 48?

or I should phrase it as:

[grim thicket]

Ah

[abstract sinew]

have you already written down 50 on that list?

the solutions to that congruence aren't integers.

they're integers mod 48

so as soon as you write down 2, you've also written down 50 and 98 and 146 and ...

[grim thicket]

Ah I understand now. That was the bit of information I was missing.

[abstract sinew]

(and -46 and ... )

[grim thicket]

Thank you very much!

[abstract sinew]

np and gl

[stuck lintel]

🍌

[low jolt]

@sacred junco 👍 thanks.

[limber crow]

can somebody sanity check me? I'm doing a chinese remainder theorem problem

my equations are x = 3 mod 7, x = 4 mod 5, and x = 1 mod 3

then N = 3*5*7 = 105

the partial products are 15 for 7, 21 for 5, and 35 for 3

multiplicative inverse of 15 mod 7 is 1

multiplicative inverse of 21 mod 5 is 1

multiplicative inverse of 35 mod 3 is -1

Then x = 15*3*1+24*4*1+35*1*-1 = 106

but that is wrong

help?

[limber crow]

nvm I figured it out I'm just a dumbass

[silver solar]

🍮

[low jolt]

I posted a similar proof on stackexchange, but I felt that it couldn't hurt to have more opinions. So here's my proof that there are infinitely many primes in the form 4k-1 that is congruent to 3 mod 4.

If $4k-1 \equiv 3 \mod4$ then the following equation is true : $$4k-4 = 4n$$ where $n \in \mathbb{Z}$,
$$k-1 = n$$
$$k = n+1$$

Since $n \in \mathbb{Z}$, then there must exist infinitely many $k$, thus not only proving that primes in the form $4k-1$ are congruent to 3 modulo 4, but also proves that every integer of the form $4k-1$ is congruent to 3 mod 4.

[sterile pumice]

Rumoden:

[stuck lintel]

Your last paragraph doesn't make sense

It's proved there are an infinite number of numbers of the form 4k-1 but it doesn't prove that an infinite number of those are prime

Also 4k-1 is congruent to 3 mod 4 trivially by the definition of mod

[low jolt]

How do I do that?

I have to prove that there are infinitely many primes in the form 4k-1?

[stuck lintel]

4k + 3 is equivalent to 4k - 1

also try a proof by contradiction

assume there exists a finite number of primes of the form 4k + 3 and see what happens

[low jolt]

Got it, thanks!

[worldly tinsel]

I have this question https://gyazo.com/e6a31bb3993c0c4056c13b3d741d1e75 which is supposed to become 4(mod 14) and I have no issues getting (2)^14 mod(14) but I'm unsure how to go from there to 4mod(14)

The only thing I can think of is simplifying it to (2^7)^2 but still not sure how to proceed

[static sparrow]

13 = -1 mod 14, and 29 = 1 mod 14 would be a good start i guess

[gilded tinsel]

umm 2^7 mod 14 is 2

@worldly tinsel

2^7 aint that big so you could easily just calculate it

[worldly tinsel]

Yeah got helped in #help-2 but thanks anyways,

[forest fractal]

can somebody explain the chinese remainder theorm to me

in simple terms

[sacred junco]

How do I prove that between integers a to (p-1)a all the numbers are congruent to unique integers mod p ?

Assuming gcd of p and a is one

[lament arch]

@sacred junco unique integers?

[sacred junco]

In fermat's little theorem proof it used inequalities. Didn't get it

Oh by a to p-1 a I meant

a, 2a, 3a to (p-1)a

[lament arch]

$$\alpha a \equiv \beta a \mod p \implies$$
$$ \implies\alpha a - \beta a \equiv 0 \mod p \implies$$
$$ \implies a(\alpha - \beta) \equiv 0 \mod p \implies$$
$$\implies a \equiv 0 \vee \alpha - \beta \equiv 0 \mod p$$

[sterile pumice]

izanbf:

[sacred junco]

is this a contradiction?

[lament arch]

yes if a is not congruent to 0 and alpha and beta are not congruent

[sacred junco]

Oh yeah I get it

thanksss

[lament arch]

i think this is correct and anything more is required

[low jolt]

having some trouble comprehending the blue part

[quick furnace]

this says "if some natural number is in S, then so's the one right above it"

[low jolt]

I see, thanks.

[hollow lark]

hey.
i need to prove that : gcd((3a+4b),(4a+5b)) = 1, while gcd(a,b) =1
i’ve tried diophantine equation and bezout identity but it doesn’t work.
can someone tell me how should i start ?

thank you !

[stuck lintel]

use euclidean algorithm

[noble jay]

@hollow lark let d = gcd(.....,....), d divides both so d divides every linear combination of both

try to get to d divides a and d divides b

[stuck lintel]

gcd((4a + 5b), (3a + 4b)) = gcd((3a + 4b), (a + b)) = gcd((a+b), b) = gcd(a, b) = 1

[hollow lark]

that's what i did ! thank you !

[drowsy cobalt]

I got a question about the average prime Gap. According to PMT, there are x/ln x primes between 0 and x. Then, if p_m is the last prime less than x, the average prime Gap should be (p_m - 2)/(x/lnx - 1) shouldn't it? If there are n primes then there will be n - 1 prime gaps and since p_m and 2 are the last and the first prime between 1 and x, the numerator should be p_m - 2.

Why is the average Gap accepted as ln x?

[sacred junco]

prime gap doesn't mean difference between 1st and last prime in that range

it means difference b/w the last and second last

or maybe im not understanding your argument

the standard way is to use PNT+ pigeonhole principle

[drowsy cobalt]

Yeah prime gap is p_n+1 - p_n right?

[sacred junco]

ye

[drowsy cobalt]

then if the last prime number less than x is p_m

then the gaps would be 3-2, 5-3, ...., p_n+1 - p_n,... p_m-1 - p_m-2, p_m - p_m-1 right?

so you add them all up

and divide by the number of prime gaps

on adding them up, you're left with p_m-1 - 2

and the number of gaps is the number of primes minus one

[sacred junco]

now you are confusing number of gaps and the gaps themselves

[drowsy cobalt]

Average prime gap = sum of all prime gaps/number of prime gaps

number of prime gaps = number of primes - 1

Wait

[sacred junco]

[drowsy cobalt]

Is the average prime gap the average of the gap between consecutive primes or between all primes?

[sacred junco]

consecutive

[drowsy cobalt]

yes so the sum of all prime gaps should be p_m - 2 shouldn't it?

[sacred junco]

sum of all prime gaps upto the mth prime, yes

[drowsy cobalt]

if p_m is the greatest prime less than x then

p_m - 2 would be the sum of all prime gaps of primes less than x

and the number of primes would be x/lnx

so the number of gaps would be one less than that

which means the average prime gap is (p_m - 2)/(x/lnx - 1)

[drowsy cobalt]

<@&286206848099549185>

[wild zinc]

average prime gap means average (ie expected) gap between two primes of (roughly) that size

so eg the expected prime gap between consecutive 50-digit primes is roughly log(10^49)

[shadow saffron]

i was wondering if there is a name for this thing and why does it work

say you want to find the smallest number with n factors

you would take the prime factors of n

subtract one from them and then use them in descening order for the exponents of the prime numbers

and this gives you the lowest number with n factors

[quick furnace]

it has to do with the number of factors a given number has

bc to find that, you can factor it into primes, take all the exponents, add 1 to each, multiply all that together, and get the desired result

for example the number $2^5 3^{11} 5^8 7^{10}$ has $(5+1)(11+1)(8+1)(10+1)$ factors

[sterile pumice]

Ann:

[shadow saffron]

why do we add/minus 1 though

and does this have a name

[wild zinc]

each factor itself has a prime factorisation that is unique up to ordering

[shadow saffron]

i dont understand

[wild zinc]

well I haven't finished explaining :^)

[shadow saffron]

oh sorry

[wild zinc]

so we just need to find the number of ways of selecting primes from the factorisation, in this case 2^5 * 3^11 * 5^8 * 7^10

so we could select 2^4, 3^7, 5^0 and 7^10

which would give us the factor 2^4 * 3^7 * 7^10

I cba to work out what that works out to as a decimal

but the point about the factor having a unique prime factorisation is that the only way to get that factor is to select those primes

now to count the number of ways to select prime factors from that:

we can pick a power of 2, 3, 5, 7 etc. independently

so it comes down to multiplying the number of possible powers for each of these

if we look at the power of 2

it can be 2^0, 2^1, 2^2, 2^3, 2^4 or 2^5

so 6 possibilities

the adding one comes from the fact that we are counting from 0 to the highest power of 2 that divides it

rather than from 1

now this is maybe a bit rambly so if there's something specific in that you don't get then ask @shadow saffron

[shadow saffron]

ok i think i understand

ok yeah, so 2^0 * 3^6 * 5^8 *7^0 is another factor?

@wild zinc

[wild zinc]

yeah

[shadow saffron]

it seems to be more of combinatorics trick then?

[wild zinc]

counting them yes

[shadow saffron]

ok, thanks for all the help

[wild zinc]

np :)

btw I'm not sure that the prime factorisation always gives you the smallest number with that many factors

you could combine the factors of 20 (or whatever you're doing) in some other way which may give something smaller

in this case it works but I think there are cases where it doesn't

[shadow saffron]

idk, i think i read somewhere someone used this method to find the smallest 3 (i dont recall how) so that they were able to find the sum of the three smallest numbers with n integers

[wild zinc]

well it gives a reasonable start

but say for 32 factors or something like that

it'll give you 2 * 3 * 5 * 7 * 11

= 2310

whereas you could do say 2^3 * 3 * 5 * 7 = 840

instead using 32 = 4 * 2 * 2 * 2

[shadow saffron]

but 4 isnt a prime factor?