#discrete-math | Mathematics | Page 167

valid wave Mar 23, 2021, 6:53 PM

#

taking the intersection

#

im not seeing how the answer wouldnt be b

#

since b would be in both parts

pale epoch Mar 23, 2021, 6:53 PM

#

you mean {b}?

valid wave Mar 23, 2021, 6:54 PM

#

yes elemnt b

#

since parts in partition must be pariwise disjoint?

#

but element b is in both partitions

#

so its confusing me

#

how the intersection isnt B

pale epoch Mar 23, 2021, 6:55 PM

#

valid wave since parts in partition must be pariwise disjoint?

this already gives you just two possibilities

#

either the parts are disjoint or they are equal

#

and i think you noticed that they cannot be disjoint, so ...

valid wave Mar 23, 2021, 6:57 PM

#

wait

#

but how can they be equal?

coral raven Mar 23, 2021, 6:57 PM

#

different names for the same thing

pale epoch Mar 23, 2021, 6:58 PM

#

valid wave but how can they be equal?

what makes you think that this is a problem?

valid wave Mar 23, 2021, 6:58 PM

#

because partitions have to be uniuqe

pale epoch Mar 23, 2021, 6:58 PM

#

you mean parts in the partition? sure

#

but what kaisheng said basically

valid wave Mar 23, 2021, 6:59 PM

#

ah

#

so

#

meaning

#

that theres nothing that interects

#

because

#

b

#

cannot be

#

in the partition of a?

pale epoch Mar 23, 2021, 6:59 PM

#

what?

#

what is a set intersected with itself?

valid wave Mar 23, 2021, 6:59 PM

#

nothing

pale epoch Mar 23, 2021, 7:00 PM

#

think again

valid wave Mar 23, 2021, 7:00 PM

#

wait

#

everything?

pale epoch Mar 23, 2021, 7:00 PM

#

what do you mean with everything?

valid wave Mar 23, 2021, 7:00 PM

#

all the elements in the set?

pale epoch Mar 23, 2021, 7:00 PM

#

the set itself, yes

valid wave Mar 23, 2021, 7:02 PM

#

but im so lost

#

1a. how b wouldnt be the answer

#

since b would be in both sets

#

could someone explain this

#

im sorry my brain is tiny

pale epoch Mar 23, 2021, 7:03 PM

#

i mean that is true, but what makes you think that only b is in both sets

valid wave Mar 23, 2021, 7:03 PM

#

since we are told that b E P_a

#

im assuming everything else would like "alternate"

#

because parts of partition have to be unique

pale epoch Mar 23, 2021, 7:04 PM

#

let's start again from the beginning

#

so $P_a$ and $P_b$ are not necessarily unique parts of the partition

vital dewBOT Mar 23, 2021, 7:04 PM

#

Lochverstärker

pale epoch Mar 23, 2021, 7:04 PM

#

since different parts in a partition are disjoint, there are two cases:

coral raven Mar 23, 2021, 7:04 PM

#

pale epoch so $P_a$ and $P_b$ are not necessarily unique parts of the partition

they're not necessarily distinct

#

they are unique in that they are the only parts which contain a, or b

#

</pedanticism>

pale epoch Mar 23, 2021, 7:05 PM

#

ye, better word

#

anyways, either $P_a = P_b$ or $P_a \cap P_b = \varnothing$

vital dewBOT Mar 23, 2021, 7:05 PM

#

Lochverstärker

pale epoch Mar 23, 2021, 7:06 PM

#

do you agree with this @valid wave ?

valid wave Mar 23, 2021, 7:07 PM

#

ohhh

#

so either its the same set

#

so the intersection would be itself

#

or

#

they are compleletly different

#

so the empty set

#

gotcah

pale epoch Mar 23, 2021, 7:07 PM

#

ye, and you figured out that $b \in P_a \cap P_b$

vital dewBOT Mar 23, 2021, 7:07 PM

#

Lochverstärker

pale epoch Mar 23, 2021, 7:07 PM

#

which rules out one of the possibilities

#

so it has to be the other

valid wave Mar 23, 2021, 7:08 PM

#

so that means they are the same?

#

but only b is in both sets>

#

not everything in partition b

coral raven Mar 23, 2021, 7:08 PM

#

no, Pa = Pb

pale epoch Mar 23, 2021, 7:08 PM

#

again, what makes you think that

#

you only know that b is in both

coral raven Mar 23, 2021, 7:08 PM

#

it never said b was the only thing in Pb

valid wave Mar 23, 2021, 7:09 PM

#

because we are told that b is in the set of P_b

#

oh

#

what loses me ig is because partitions are usaully unique

#

so like in only 1 part of the parition

#

we are then told that b is in both parts of the parttion

coral raven Mar 23, 2021, 7:10 PM

#

yeah so they have to be the same part

#

the parts have to be unique, the names don't have to be

#

there's only one part which contains b but you can call it fifteen different things

#

in this case it turns out that Pa and Pb are two names for the same thing

valid wave Mar 23, 2021, 7:14 PM

#

how can we just make a be in both as well?

coral raven Mar 23, 2021, 7:15 PM

#

a is in Pa and Pa and Pb are the same thing so a is in Pa and Pb

valid wave Mar 23, 2021, 7:15 PM

#

how are they the same thing when Pa = ab and Pb = b

coral raven Mar 23, 2021, 7:15 PM

#

look

valid wave Mar 23, 2021, 7:15 PM

#

😦

coral raven Mar 23, 2021, 7:15 PM

#

Pa isn't just a and b

#

and Pb isn't just b

#

think of sets, generally, as boxes

#

so it's like

#

if you're told that there's an apple in the box

#

that doesn't mean there's not a banana in the box

#

if you're told there's only an apple in the box, then that would be true

#

so

#

we saw that both a and b are in Pa, right?

valid wave Mar 23, 2021, 7:17 PM

#

yes

coral raven Mar 23, 2021, 7:17 PM

#

but we also saw that this meant that Pa and Pb were the same thing

#

two names for the same box

#

capiche?

#

so if a and b are both in Pa, and Pa and Pb are the same thing, then a and b are both in Pb

valid wave Mar 23, 2021, 7:19 PM

#

ahhhh

#

can you explain the same name jump

#

i get everything other than that

coral raven Mar 23, 2021, 7:19 PM

#

ok so

valid wave Mar 23, 2021, 7:19 PM

#

the jump that they are the same

coral raven Mar 23, 2021, 7:19 PM

#

when you have two parts

#

then the intersection of them is either everything or nothing

#

so if they share anything, then you know they share everything

#

and if they share everything, they're the same thing

#

it's like saying 2 = 2

valid wave Mar 23, 2021, 7:23 PM

#

ahhh gotcah

#

so

#

the question saying that

#

B E P_a

#

is kind saying that

#

A E P_b

#

ahhh so the question saying B E P_a

#

we know that the intersection is gonna be everything

coral raven Mar 23, 2021, 7:25 PM

#

yes

valid wave Mar 23, 2021, 7:25 PM

#

OHHH

#

so if it said

#

B E/ P_a

#

that means

#

its nothing

coral raven Mar 23, 2021, 7:25 PM

#

uhhh

#

yes

#

they'd just be two completely different parts

#

nothing interesting to say

valid wave Mar 23, 2021, 7:26 PM

#

ok ok

#

i get it now

#

lassttt question

#

if we have a partition

#

isnt it supposed to be uniuqe

#

like how can we say b is in both

#

that idea seems weird

coral raven Mar 23, 2021, 7:27 PM

#

they're the same part

valid wave Mar 23, 2021, 7:27 PM

#

but ill worry about that later

coral raven Mar 23, 2021, 7:27 PM

#

two names for the same part

valid wave Mar 23, 2021, 7:27 PM

#

ahhh

#

OHHH

coral raven Mar 23, 2021, 7:27 PM

#

you're allowed to have multiple names for the same part

valid wave Mar 23, 2021, 7:27 PM

#

thats waht you meant

#

ohhhh

coral raven Mar 23, 2021, 7:27 PM

#

just not more than one part with something in

#

yeah

valid wave Mar 23, 2021, 7:31 PM

#

🤯

#

thanks for taking the time to explain

sand cipher Mar 24, 2021, 1:16 AM

#

need help with this

#

this is a test review but idk how to do it

#

i need help to understand this ch for tomorrow test

#

honestly whichever we review doesn't matter

#

since it's just a review, but i need any help to understand

amber prism Mar 24, 2021, 1:23 AM

#

I mean, 4 is pretty obvious

sand cipher Mar 24, 2021, 1:27 AM

#

for 4 i can just write smthing like sqrt2 and sqrt 2 = 2

#

rite?

naive saffron Mar 24, 2021, 1:40 AM

#

Yes

#

So it’s false

amber prism Mar 24, 2021, 1:45 AM

#

sand cipher for 4 i can just write smthing like sqrt2 and sqrt 2 = 2

I mean even "better" is sqrt(3) and sqrt(12) since we're not obviously squaring a square root

kind geode Mar 24, 2021, 2:14 AM

#

second one is quite easy too

#

u have n^2+n+1, that becomes n(n+1) + 1

#

and you know that n(n+1) or the multiplication of two consecutive integers will always be even, and then u add 1 to an even number making it odd

#

third one i believe u solve using contraposition (ie prove that if r is rational, that r^3 will also be rational)

sand cipher Mar 24, 2021, 2:56 AM

#

n^2 mod n = 0
&
4 mod 2 = 0
rite??

obtuse lance Mar 24, 2021, 3:03 AM

#

yep

sand cipher Mar 24, 2021, 3:21 AM

#

can someone explain number 8 pls

obtuse lance Mar 24, 2021, 3:31 AM

#

it's basically the same thing as 1

last timber Mar 24, 2021, 3:31 AM

#

but if you turn it 90 degrees you get infinity!

naive saffron Mar 24, 2021, 3:34 AM

#

sand cipher can someone explain number 8 pls

it's the magic number where if you see it it means you're reading an applied math book

obtuse lance Mar 24, 2021, 3:34 AM

#

lol for the record my response is actually legitimate

naive saffron Mar 24, 2021, 3:35 AM

#

obtuse lance Mar 24, 2021, 3:35 AM

#

sand cipher need help with this

problem 8 is like problem 1, just do induction using the result from problem 1

naive saffron Mar 24, 2021, 3:35 AM

#

jk yeah just apply 1. and you'll get the answer

orchid pine Mar 24, 2021, 5:58 AM

#

is the ternary expansion in the tertiary cantor set supposed to be infinite?

orchid pine Mar 24, 2021, 6:15 AM

#

can i represent intervals [2,1]

stray reef Mar 24, 2021, 6:15 AM

#

[2,1], taken literally, will refer to the empty set

orchid pine Mar 24, 2021, 6:18 AM

#

intervals are just a set showing a range though

stray reef Mar 24, 2021, 6:18 AM

#

i mean

#

why do you need to represent intervals with the left endpoint bigger than the right

orchid pine Mar 24, 2021, 6:21 AM

#

if i represent outputs of a function as an interval then it would make it more clear

#

if the outputs are decreasing

stray reef Mar 24, 2021, 6:24 AM

#

...

#

not really

#

the range of a function which decreases from 2 to 1 is still [1,2]

viral sandal Mar 24, 2021, 2:43 PM

#

Any books or resource I can learn discreet math from scratch

#

Any recomendations?

frigid abyss Mar 24, 2021, 3:38 PM

#

im confused about how to go about solving this recurrence relation given that a0 = 1

#

i solved the characteristic equation and got that r=2n

stray reef Mar 24, 2021, 3:39 PM

#

??

#

this isn't a linear recurrence

#

the solution is $a_n = 2^n n!$

vital dewBOT Mar 24, 2021, 3:40 PM

#

Ann

stray reef Mar 24, 2021, 3:40 PM

#

as can be seen by simplifying 2 * 4 * 6 * ... * 2n

frigid abyss Mar 24, 2021, 3:41 PM

#

wait dont you solve recurrences by finding the roots of the characteristic equation

#

im confused

stray reef Mar 24, 2021, 3:42 PM

#

this only works for linear recurrences with constant coefficients

#

which are a very specific class of recurrence

frigid abyss Mar 24, 2021, 3:43 PM

#

oh you can only use the characteristic equation technique for linear homogeneous recurrence relation with constant coefficients

#

so for that one i have to use iteration?

stray reef Mar 24, 2021, 4:01 PM

#

idk if you "have to" use anything

frigid abyss Mar 24, 2021, 4:05 PM

#

#

#

i dont get how they got the part i put the brackets around

#

where did the ... x2 x 1 x a n-n come from

stray reef Mar 24, 2021, 4:10 PM

#

they applied the recurrence n times

frigid abyss Mar 24, 2021, 4:13 PM

#

right i get it now thx

stray reef Mar 24, 2021, 4:54 PM

#

how can you build a valid codeword of length n from valid codewords of length less than n?

#

thats the question you should think about

chilly granite Mar 24, 2021, 5:04 PM

#

what is the best prime factorization algorithm?

unreal stump Mar 24, 2021, 5:12 PM

#

There is no good prime factorisation algorithm

weary tiger Mar 24, 2021, 5:12 PM

#

Let $a_{n-1}$ be a valid codeword of length n-1, so it has an even number of 0's in it. $a_{n}$ is obtained from $a_{n-1}$ by adding an extra decimal digit, in a way that preserves the given condition, so that extra digit can be anything except 0, otherwise, this would imply an odd number of 0's in $a_{n}$

vital dewBOT Mar 24, 2021, 5:13 PM

#

Laïka

stray reef Mar 24, 2021, 5:13 PM

#

clashing notation

unreal stump Mar 24, 2021, 5:13 PM

#

The best we have is checking if a prime p divides a number(n) and find the number of times it divides the number(let that be k,i.e.,k is the largest number such that p^k divides n) and writing n=p^k*(n/p^k) and repeating with n/p^k

#

afaik

stray reef Mar 24, 2021, 5:21 PM

#

who pung me

stray reef Mar 24, 2021, 5:36 PM

#

n indicates the length of the codeword

#

also i think i got it

#

you can either

take an invalid codeword of length n-1 and attach a 0 to it
take a valid codeword of length n-2 and attach 00 to it
take a valid codeword of length n-2 and attach two non-zero digits to it

#

so... $a_n = (10^{n-1} - a_{n-1}) + 82a_{n-2}$ i guess?

vital dewBOT Mar 24, 2021, 5:37 PM

#

Ann

stray reef Mar 24, 2021, 5:42 PM

#

the possible pairs of digits to attach to a codeword of length n-2 yeah

short wyvern Mar 24, 2021, 6:06 PM

#

Привет @stray reef , не подскажешь случаем, тут ведь получается, что функция определена везде, ведь мы не достигаем случая, где у=4? По логике материала лекций проблем нет, но зачем тогда давать такое задание...
PS прим. рек функции вроде относятся к дискре
PPS прости за прямое обращение, я помню ещё в прошлом году что-то спрашивал по дискре и ты мне тогда помогла, надеюсь выглядело не крипово

stray reef Mar 24, 2021, 6:09 PM

#

стрелка вверх значит "не определено"?

#

мне как-то неочевидно, что здесь никогда не достигается случай y=4

short wyvern Mar 24, 2021, 6:09 PM

#

Да, неопределённость

stray reef Mar 24, 2021, 6:10 PM

#

так, а как работает оператор \mu y?

short wyvern Mar 24, 2021, 6:10 PM

#

Хм, просто же подставляя любые натуральные х, нам почти всегда должно хватить у=0 или у=1, чтобы функция была больше 1

short wyvern Mar 24, 2021, 6:11 PM

#

stray reef так, а как работает оператор \mu y?

Наименьшее число у, такое что

stray reef Mar 24, 2021, 6:11 PM

#

ага

#

$1 \dot - |g(y)-x| = 0$ вроде бы равносильно $|g(y)-x| \geq 1$

#

так

#

а забыла команду для этого минуса с точкой

short wyvern Mar 24, 2021, 6:11 PM

#

\dot-

stray reef Mar 24, 2021, 6:11 PM

#

а

#

прикольно, я думала, что свой макрос у него будет

#

ладно

vital dewBOT Mar 24, 2021, 6:12 PM

#

Ann

stray reef Mar 24, 2021, 6:12 PM

#

херово выглядит, но ладно

short wyvern Mar 24, 2021, 6:12 PM

#

Да

stray reef Mar 24, 2021, 6:12 PM

#

ну да, вроде везде получается твоя функция определена

#

а в чем задание было?

short wyvern Mar 24, 2021, 6:13 PM

#

Определить где она определена и какие значения принимает в точках где определена

stray reef Mar 24, 2021, 6:13 PM

#

ну и

short wyvern Mar 24, 2021, 6:13 PM

#

То есть там везде получается что 0, кроме f(1)

#

Просто странно, я ожидал какую-то возню, вот и подумал, что может я что-то не так интерпретирую

stray reef Mar 24, 2021, 6:14 PM

#

иногда возни нет

#

и возня состоит в том, чтобы определить, что возни нет

short wyvern Mar 24, 2021, 6:14 PM

#

🤣

#

Спасибо

prisma cypress Mar 24, 2021, 6:28 PM

#

okay i could use some assistance as for how i get the other value in this... its not making much sense

stray reef Mar 24, 2021, 6:29 PM

#

just distribute

#

$38 - 9 \cdot (42 - 1 \cdot 38) = 38 - 9 \cdot 42 + 9 \cdot 38 \ = -9 \cdot 42 + 10 \cdot 38$

vital dewBOT Mar 24, 2021, 6:29 PM

#

Ann

prisma cypress Mar 24, 2021, 6:30 PM

#

um... im still confused

stray reef Mar 24, 2021, 6:30 PM

#

don't overthink it

prisma cypress Mar 24, 2021, 6:31 PM

#

err...

#

im still lost...

stray reef Mar 24, 2021, 6:36 PM

#

cause youre overthinking it

#

i literally all but gave you the answer

prisma cypress Mar 24, 2021, 6:39 PM

#

... but im not seeing how distributing is supposed to give that 10...

stray reef Mar 24, 2021, 6:49 PM

#

you couldve said that outright instead of leaving me guessing, just sayin'

#

38 + 9*38 = 10*38.

prisma cypress Mar 24, 2021, 6:54 PM

#

now... to be fair... my initial post did ask for help on how to get the other value. but then this is just... uh... i think i see that now..?

hybrid crown Mar 24, 2021, 8:46 PM

#

I need help getting over this hill

#

#

#

this is what they mean by one line notation

#

#

--

#

In the question there are three parts (a) (b) and (c)

#

I've done a and b a while ago but then got stuck with c and then dropped the book I was reading for a little bit

#

The first two screenshots are of the question

#

The third is from earlier in the text to clarify if needed

#

I will also explain the idea for the solutions I had in mind for a and b

#

In spoilers in case someone wants to give it a go

#

For a || every permutation can be matched up with a corresponding one that comes from reversing the elements.. A c b d to d b c a for example and then considering the increasing segments||

#

For b || when we have n-1 elements permuted there are n spaces where the next and largest element can be inserted. If the largest is placed at the end of a segment it will not generate a new segment. Thus we are worried about f(n-1,k) case in this situation and there K such spots so the k*f(n-1,k) term. Similarly for the other case there are n-(k-1) for the other case since we need to consider perms with k-1 segments and not K since we would be increasing them in this process. And hence the (n+1-k)*f(n-1,k-1) term. These are all the possibilities when adding the nth element into a n-1 perm. Either you increase the number of segments or you don't. And then you measure with the help of that wrt what f(n, k) you want. ||

#

B looks long only because there are two terms which I had to explain

hybrid crown Mar 24, 2021, 9:23 PM

#

(pls ping BTW thanks a ton for looking)

fleet hare Mar 24, 2021, 9:53 PM

#

Yo programming 2 , calc 3 and discrete math . I am taking those next semester

#

is this going to be hell? or is it doable

weary tiger Mar 24, 2021, 10:28 PM

#

fleet hare Yo programming 2 , calc 3 and discrete math . I am taking those next semester

discrete maths will be pretty tough lmao

fleet hare Mar 24, 2021, 10:33 PM

#

fuck

minor dagger Mar 24, 2021, 10:37 PM

#

It might be hard it might not it varies

#

You don't know until you do it

autumn star Mar 25, 2021, 12:24 AM

#

Is anyone able to help with this ?

lime jolt Mar 25, 2021, 1:40 AM

#

Can anyone explain to me why

bool someFunc(int a, int b) {
  for(something) {
    if(something) {
}
}
}

Would be T(n) = n - 1?

kind geode Mar 25, 2021, 3:49 AM

#

lime jolt Can anyone explain to me why ``` bool someFunc(int a, int b) { for(something)...

lol what is this a function takes two ints loops "something" then if ("something") do nothing?

lime jolt Mar 25, 2021, 3:50 AM

#

I mean, it is no specific function lol

#

If there was code in there it would only be one for loop and one if statement inside it

kind geode Mar 25, 2021, 3:51 AM

#

wait so whts the connection from the fucntion and T(n) = n -1

lime jolt Mar 25, 2021, 3:52 AM

#

I am just trying to figure out a recurrence relation formula for the function

#

And justify it

#

Let's just say I had that T(n)=n - 1

#

Forget the code lol

#

If I were to justify it, would it just be, input a size for the function?

#

So T(1) = 0 because and array of size one doesn't do anything?

hybrid crown Mar 25, 2021, 8:02 AM

#

autumn star Is anyone able to help with this ?

Write the equation it'll be smth like a/b + p/q = k

#

Take LCM and move one of the terms to the right and see what observation you can make while keeping in mind b does not divide a and q does not divide p

urban saddle Mar 25, 2021, 9:36 AM

#

is there any mechanical/easy way to find all subsets of a given set?

last timber Mar 25, 2021, 9:55 AM

#

for finite one - enumerate it and use char function

pale epoch Mar 25, 2021, 10:15 AM

#

subsets of finite (or more generally countable) sets corresponds to binary strings

hybrid crown Mar 25, 2021, 12:36 PM

#

^^ If you are doing it in a program you could maybe say the nth subset is the one you get from taking the binary form of n and then using the corresponding elements

#

so in a way you already have all the subsets enumerated and available.

balmy hornet Mar 25, 2021, 2:57 PM

#

We are doing this in my discrete math class, but if it doesnt fit here please tell me! to confirm this answer, −18 mod 5 = 2?

stray reef Mar 25, 2021, 3:27 PM

#

yes

balmy hornet Mar 25, 2021, 4:36 PM

#

stray reef yes

Thank you!

#

So I dont understand my prof’s notes and its disordered so I don’t know where step 1 is to approach this problem. Multiply 1111(subscript 2) by 4 = ________(subscript 2)

stray reef Mar 25, 2021, 4:37 PM

#

you mean subscript 2?

#

so like, 1111 in binary?

balmy hornet Mar 25, 2021, 4:38 PM

#

stray reef so like, `1111` in binary?

Yes sorry ill edit that so it makes more sense. I didnt even realize i had written subset

stray reef Mar 25, 2021, 4:39 PM

#

okay...

#

do you know what 4 looks like when you write it in binary?

#

👻

balmy hornet Mar 25, 2021, 4:56 PM

#

stray reef do you know what 4 looks like when you write it in binary?

Sorry for the late message. but 0100?

stray reef Mar 25, 2021, 4:56 PM

#

100, yes

#

so multiplying by 4 looks like shifting to the left by two positions in binary

balmy hornet Mar 25, 2021, 4:58 PM

#

stray reef so multiplying by 4 looks like shifting to the left by two positions in binary

mhm ok so i would then do that to 1111?

stray reef Mar 25, 2021, 4:58 PM

#

....yes

balmy hornet Mar 25, 2021, 4:59 PM

#

stray reef ....yes

so then it would just be 11110000?

stray reef Mar 25, 2021, 4:59 PM

#

why are you multiplying by 16 and not by 4 thonk

balmy hornet Mar 25, 2021, 5:01 PM

#

stray reef why are you multiplying by 16 and not by 4 <:thonk:406575732563902485>

Excuse that sorry. 111100

stray reef Mar 25, 2021, 5:01 PM

#

there we go

#

also you really did not need to reply-ping me at every single message

balmy hornet Mar 25, 2021, 5:02 PM

#

sorry sorry habit on other servers lol

robust mango Mar 25, 2021, 5:51 PM

#

what's troubling you?

#

Do you know what a geometric sequence is?

#

it's a sequence of numbers that differ by a common ratio

#

You are given that the first term in the geometric sequence is 2

#

and then also given that the ratio is 2

#

The ratio is used on the first term to find the second term

#

and it's done by multiplying

#

We multiply the first term(2) by the ratio(2) to get the second term

#

Which is 4

#

then the second term multiplied by the ratio to get the third term

#

and so on

#

yes

#

similarly, for an arithmetic sequence

#

instead of multiplying by the ratio, we add the common difference to the previous term to find the next term

#

Difference means difference between the next and previous term

#

The formula for difference in an arithmetic sequence is d = Next - Previous

#

Similarly for ratio, it's r = next/previous

#

we would subtract if the difference was negative

#

yes

#

yes

#

yeah just put that down

#

hm

#

Okay so the rule is that if (a,b) is in S, then we must have (a+1,b+2) and (a+1,b+1) in S

#

Since (0,0) is in S, we must have (0+1,0+2) and (0+1,0+1) in S, that is (1,2) and (1,1) in S

#

now since you have (1,2) in S, use the rule again

#

since you have (1,1) in S, use the rule again

#

The rule says, if you have (a,b)

#

Then you must have (a+1,b+2) and (a+1,b+1) in S

#

SInce we had (0,0), we used the rule and concluded that we have (1,1) and (1,2)

#

Now since we have (1,1)

#

We must use the rule again

#

And since we have (1,2), we must use the rule again

robust mango Mar 25, 2021, 6:21 PM

#

lmao

weary tiger Mar 25, 2021, 6:21 PM

#

?

robust mango Mar 25, 2021, 6:21 PM

#

@tepid fulcrum why'd u delete all the messages

weary tiger Mar 25, 2021, 6:21 PM

#

oh lol

robust mango Mar 25, 2021, 6:21 PM

#

was that a test

#

why delete

#

i see

weary tiger Mar 25, 2021, 6:23 PM

#

lmao

tepid fulcrum Mar 25, 2021, 6:24 PM

#

see it lagging the server

weary tiger Mar 25, 2021, 6:26 PM

#

it was a test for sure

robust mango Mar 25, 2021, 6:29 PM

#

lol

#

yeah

#

rip

valid wave Mar 25, 2021, 8:13 PM

#

hi just making sure im understanding

#

'

#

when making groups from this set of numbers

#

we divide by the amount of groups we have

#

when we make our permutations

#

to account for switching the groups into different orders right?

weary tiger Mar 25, 2021, 8:27 PM

#

looks good @valid wave

valid wave Mar 25, 2021, 8:33 PM

#

thanks

valid wave Mar 25, 2021, 8:59 PM

#

also

#

#

wouldnt that second line with two astriks mean that x has two outputs?

#

#

but it says it has exactly 1

#

and why does only the first set have to map to something for it to be a function

#

oh wait, i think the first set is the domain?

#

but still im lost

#

even the idea of saying f(x) = f(y)

#

doesnt that mean a function is mapping to the same image?

kind geode Mar 25, 2021, 9:51 PM

#

hey for questions like these do i just substitute the given a_n into the recurrence relation, if it is a solution i should get back the a_n i sub in correct? if so I also wanna know what the solution really means?

Screen_Shot_2021-03-25_at_5.50.32_PM.png

#

https://www.slader.com/discussion/question/show-that-the-sequence-an-is-a-solution-of-the-recurrence-relation-an-an1-2an2-2n-9-if/

Slader

Slader :: Homework Answers and Solutions

Tomorrow's answer's today! Find correct step-by-step solutions for ALL your homework for FREE!

#

this is the solution but i dont undertstnad it

static rapids Mar 25, 2021, 11:28 PM

#

#

how would you use inductive definition with binary functions and predicates

#

im tryin to do the first question rn

#

if i understand 1 I wanna try 2 on my own

static rapids Mar 25, 2021, 11:48 PM

#

<@&286206848099549185>

kind geode Mar 26, 2021, 2:27 AM

#

also a set of real numbers is never countable rgt, even if u have a finite number of 1's or 0's in its decimal

faint narwhal Mar 26, 2021, 2:28 AM

#

Uh what?

kind geode Mar 26, 2021, 2:28 AM

#

Screen_Shot_2021-03-25_at_10.28.22_PM.png

#

for 1c and d

#

i beleive its not countable rgt

#

dispite having limited 1's and 0's

faint narwhal Mar 26, 2021, 2:29 AM

#

I'm not sure what you mean by "having limited 1's and 0's"

kind geode Mar 26, 2021, 2:29 AM

#

OHH

#

sorry that was a different quesiton

#

this one is consiting of all 1's in decimal reppresentation

#

4c)

faint narwhal Mar 26, 2021, 2:30 AM

#

so why do you think its uncountable?

kind geode Mar 26, 2021, 2:30 AM

#

well just with real numbers in general thers always goanne be a number in between "a" and "b" rgt

#

so my assumption is any real number set is uncountable?

faint narwhal Mar 26, 2021, 2:31 AM

#

Uh

#

by real number set, do you just mean a set of real numbers?

kind geode Mar 26, 2021, 2:31 AM

#

like R all real numbers

faint narwhal Mar 26, 2021, 2:31 AM

#

I mean

#

R is uncountable yes

#

But it's not because "thers always goanne be a number in between "a" and "b""

kind geode Mar 26, 2021, 2:32 AM

#

ohoh sorry this was the question yea i ss'd the wrong one thats why i was lowkey foncfusedd too

Screen_Shot_2021-03-25_at_10.31.57_PM.png

#

this 3c) not containing 0 in decimal representation

#

is this uncountable?

faint narwhal Mar 26, 2021, 2:33 AM

#

what do u think

kind geode Mar 26, 2021, 2:33 AM

#

i think uncountabel? lool

faint narwhal Mar 26, 2021, 2:33 AM

#

and why?

kind geode Mar 26, 2021, 2:33 AM

#

cause u cant list all real numbers??

#

yea

#

uh

#

thats all lmao not rll sure

faint narwhal Mar 26, 2021, 2:34 AM

#

why can't you list all real numbers?

#

This isn't even all the real numbers too

kind geode Mar 26, 2021, 2:36 AM

#

um

#

yea like theres explainations online i jsut dont unerstand them like this

#

Screen_Shot_2021-03-25_at_10.41.02_PM.png

faint narwhal Mar 26, 2021, 2:41 AM

#

uhh

#

I'm not sure where you found this answer but this isn't correct

kind geode Mar 26, 2021, 2:42 AM

#

are u sure i find this answer almost everywhere

Screen_Shot_2021-03-25_at_10.42.29_PM.png

#

all says uncountable

faint narwhal Mar 26, 2021, 2:42 AM

#

For example, the rational numbers also has this property that between any two real numbers, there's a rational, but the rationals are countable

#

I mean, the answer is fine, the reasoning is not

kind geode Mar 26, 2021, 2:43 AM

#

ohhh i see

#

oh waitttt

kind geode Mar 26, 2021, 2:45 AM

#

faint narwhal I mean, the answer is fine, the reasoning is not

mhm tryna spill the beans on the reasoning 😉

faint narwhal Mar 26, 2021, 2:45 AM

#

You should go figure out why R is uncountable

kind geode Mar 26, 2021, 2:46 AM

#

well thats just cause u cant list the numbers between like 0 and 1 rgt

#

and so for all realnumbers its not possuible to have a 1-1 correspondence with natruak numbers

faint narwhal Mar 26, 2021, 2:46 AM

#

this doesn't really make sense

#

how do you know you can't list all the numbers?

kind geode Mar 26, 2021, 2:47 AM

#

mhm now u making me think everything is countable lmao

faint narwhal Mar 26, 2021, 2:48 AM

#

The thing to look up is Cantor's diagonal argument

#

but I feel like you should've learned this in your class

kind geode Mar 26, 2021, 2:48 AM

#

oh this is the chart rgt

#

danm yea i did but a while ago

#

ohhhh ok i see basically if u construct a real number from the diagaol of previous real numbers u will have a new number

#

meaning u can always create a different number hence u cannot list EVERY number

#

ya?

faint narwhal Mar 26, 2021, 2:54 AM

#

Yeah that's the idea

#

so you want to try to find a way to adapt that proof to the problems you have

kind geode Mar 26, 2021, 2:57 AM

#

OHHH

#

so basically uncountable cause u can construct a new real number from diagonals even if 0’s aren’t present

#

so even if u tak out all 1,3,9 for instance still uncountable

faint narwhal Mar 26, 2021, 2:59 AM

#

yea

kind geode Mar 26, 2021, 3:02 AM

#

noice ty

fleet latch Mar 26, 2021, 3:09 AM

#

how do i approach this question

valid wave Mar 26, 2021, 7:42 AM

#

hi

#

quick question

#

for proving a function is one to one

#

#

why would we prove that f(x1) is the same as f(x2)

#

wouldnt that mean we get the same output?

faint narwhal Mar 26, 2021, 7:44 AM

#

You're not proving that f(x1) is the same as f(x2)

#

you're assuming that f(x1) is the same as f(x2) and proving this must mean that x1 = x2

valid wave Mar 26, 2021, 7:45 AM

#

oh

#

meaing that they are the same number

#

so every unique number

#

gives us a different image?

#

🤯

faint narwhal Mar 26, 2021, 7:45 AM

#

right

#

thats what it means to be one to one

valid wave Mar 26, 2021, 7:45 AM

#

ohhh shitttt

#

ok that makes sesne

#

the explanation was confusing me

#

thank sm

#

so pretty much proving this means that we are showing that two random nums in the set give the same value

#

which means they are the same number

#

so any different number will also have a unique iamge

#

time to practice thanks

#

thanks again

short wyvern Mar 26, 2021, 10:20 AM

#

I’m trying to figure out yet another exercise. Here is my reasoning and I wonder if that’s the correct way to approach the problem.
PR as primitive recursive

worthy patrol Mar 26, 2021, 3:32 PM

#

Hey guys this question I can’t get, I’ve gotten 14, 16, 17, 52 and they have all been wrong, would anyone be able to help me?

#

uncut kelp Mar 26, 2021, 4:28 PM

#

Hey if I define my hash function as

h(x) = ( ( x / 10^0) % 10 ) + ( ( x / 10^1) % 10 ) + ( ( x / 10^2) % 10 ) + ............ ( until x became 0 )

Can I inverse this hash function I don't know how can I make subject x from this modulo operation

If I am asking in wrong channel please let me know.

pale epoch Mar 26, 2021, 4:33 PM

#

this is not bijective, so how would you "reverse" this?

uncut kelp Mar 26, 2021, 4:37 PM

#

oh sorry we can't do this we have to try all possibilities in any way to crack hash password

zinc moss Mar 26, 2021, 11:01 PM

#

need help

last flicker Mar 26, 2021, 11:21 PM

#

well assume the negation(n/(n+2)>=n/(n+1)) and prove that it leads to nonsense

#

it may help to remember that n being in Z+ implies that n, n+1 and n+2 are all >0

#

for instance, if you were able to assume the negation and prove 1>=2, that would be a contradiction

broken kiln Mar 27, 2021, 12:15 AM

#

"Find the number of permutations (as a function of the derangement numbers) of 1,2,...,n in which exactly k of the n numbers are in their correct position"

Little confused on how to approach this question. I know derangement numbers are valid if none of the original numbers are in their original position. So would I find how many positions that is, then take the factorial of that?

#

Also there would be a formula as the solution opposed to an actual value right? Because n and k are not defined, so it has to be generalized, right?

#

I'm also not exactly sure what 'their correct position' is referring to

lyric pumice Mar 27, 2021, 1:09 AM

#

Essentially, you are to calculate the number of derangements for each sub-list that contains n-k numbers.

#

@broken kiln

#

You can express the number of derangements of a list of x numbers as D(x).

broken kiln Mar 27, 2021, 1:43 AM

#

@lyric pumice So would it be something like D(x) = (n/x) + D(n-x)? So we are finding the number of permutations with (n/x) using the formula n! / (r! (n - r)!) and then the D(n-x) to iterate through the different sets?

lyric pumice Mar 27, 2021, 1:44 AM

#

@broken kiln No.

#

Derangements of a list of n-k numbers are counted by D(n-k).

#

Then there are different ways to choose a sub-list of n-k numbers from a list of n numbers.

#

How many ways are there?

broken kiln Mar 27, 2021, 1:52 AM

#

I definitely think I'm missing some fundamentals here, because I am so confused. Should I completely forget about using the permutation formula?

#

d(n-1) / n! ways?

#

@lyric pumice We should be decreasing each time right?

lyric pumice Mar 27, 2021, 2:44 AM

#

There are n choose k ways. @broken kiln

zinc moss Mar 27, 2021, 6:08 AM

#

how would go with this one?

stray reef Mar 27, 2021, 6:08 AM

#

you could go through the same algebra as you would to solve this equation, but with more rigor/formality

slow vale Mar 27, 2021, 8:14 AM

#

I've been learning combination type questions and have been having quite the conundrum. I've encountered quite a few questions similar to something like "x1+x2+x3+x4=30, find how many integer solutions there are" and keep finding conflicting information from my textbook and teacher. The textbook and homework gives the answer of the combination of (30+4-1,30)=(33,30), but my teacher and other websites say it should be something like (33,4). Which one is truly right?

last timber Mar 27, 2021, 8:19 AM

#

@slow vale

#

wait

#

you have integer solutions

#

but these are infinitely many

slow vale Mar 27, 2021, 8:20 AM

#

I should specfic

#

x1....x4 are nonnegative integers

#

sorry

last timber Mar 27, 2021, 8:20 AM

#

ok so then

vital dewBOT Mar 27, 2021, 8:22 AM

#

Commander Vimes

last timber Mar 27, 2021, 8:22 AM

#

basically this formula

slow vale Mar 27, 2021, 8:22 AM

#

so it would be (33,30) combination correct

last timber Mar 27, 2021, 8:23 AM

#

yes (33, 30) is correct

slow vale Mar 27, 2021, 8:23 AM

#

Ok so to expand on that, I was given a practice question like this, and it made me think I had been doing this all wrong

last timber Mar 27, 2021, 8:24 AM

#

slow vale Mar 27, 2021, 8:24 AM

#

I was doing some practice quesitons and came across this, and it was just like another question I had done, but I had gotten this one wrong and was confused.

last timber Mar 27, 2021, 8:24 AM

#

what ? means

slow vale Mar 27, 2021, 8:24 AM

#

I assume

#

its <=

last timber Mar 27, 2021, 8:25 AM

#

welll

slow vale Mar 27, 2021, 8:25 AM

#

Because thats what the other similar questions ive done were

last timber Mar 27, 2021, 8:25 AM

#

look

slow vale Mar 27, 2021, 8:25 AM

#

Ik how to do it

#

or so i thought

#

but the answer is (33,5)

#

when I thought it would be (33,29)

last timber Mar 27, 2021, 8:25 AM

#

usually there are >= tho

slow vale Mar 27, 2021, 8:26 AM

#

I meant that

#

sorry

last timber Mar 27, 2021, 8:26 AM

#

well then look

vital dewBOT Mar 27, 2021, 8:26 AM

#

Commander Vimes

slow vale Mar 27, 2021, 8:27 AM

#

I understand that I think

#

My steps were x1+x2+x3+x4+x5=50

#

50-21 (the given inequalites) = 29

#

29+5-1=33

last timber Mar 27, 2021, 8:28 AM

#

why 21

#

,calc 3+4+2+12

vital dewBOT Mar 27, 2021, 8:28 AM

#

Result:

last timber Mar 27, 2021, 8:28 AM

#

nvm

#

i am dumb

#

kekw

slow vale Mar 27, 2021, 8:28 AM

#

i just dont understand

#

why they use 5, instead of 29

#

for the 2nd element of the combination

last timber Mar 27, 2021, 8:29 AM

#

tho they should use 5-1=4

slow vale Mar 27, 2021, 8:30 AM

#

the answer they give nonsimplified is 33!/(5!28!), which is (33,5) right

last timber Mar 27, 2021, 8:30 AM

#

yes

slow vale Mar 27, 2021, 8:30 AM

#

so where am I wrong

#

see, theres also a similar problem

#

You could solve it the same way, x1+x2+x3+x4+x5=14

#

but again, the answer is similar in that its (18,5), not what I would think (18,14)

last timber Mar 27, 2021, 8:32 AM

#

i dunno then

#

hmmm

slow vale Mar 27, 2021, 8:33 AM

#

But in the homework, we have questions and answers like this https://www.slader.com/textbook/9780534203771-bundle-discrete-mathematics-with-applications-3rd-student-solutions-manual-3rd-edition/355/exercise-set/13/

Slader

Slader :: Homework Answers and Solutions

Tomorrow's answer's today! Find correct step-by-step solutions for ALL your homework for FREE!

#

Where what I would think to be true is true

#

So Im just scared on the test, which method should I use?

last timber Mar 27, 2021, 8:35 AM

#

well the one i posted is proved to be correct..

slow vale Mar 27, 2021, 8:37 AM

#

I also found this on a website which is so odd to me, because it contradicts that I think https://www.andrew.cmu.edu/course/15-251/Recitations/recitation03/rec03_sol.pdf

#

which confused me even more

#

wait, nvm they are equivlent arent they?

#

(44,4)=(44,40), because of binomial theory right

#

you know, what, I think my teacher simply forgot the -1 on the second element, so instead of (33, 4) they did (33,5)

#

they forgot how to do it with every similar problem

#

the dodgeball question should end with (18,4), but they wrote (18,5)

last timber Mar 27, 2021, 8:45 AM

#

could happen

slow jewel Mar 27, 2021, 12:29 PM

#

Anyone know how to do 5.60a

obtuse lance Mar 27, 2021, 12:29 PM

#

,rotate

vital dewBOT Mar 27, 2021, 12:29 PM

#

weary tiger Mar 27, 2021, 12:41 PM

#

Think of finding the number of ways not to answer the first two questions

#

then subtract this from the total number of answering 10 question out of 13

#

@slow jewel

slow jewel Mar 27, 2021, 12:44 PM

#

no idea mate

#

dont know how to find the number of ways not to choose the first two questions

weary tiger Mar 27, 2021, 12:47 PM

#

Actually there is a much more simpler way to solve this

slow jewel Mar 27, 2021, 12:47 PM

#

i just guessed c(11,8)

weary tiger Mar 27, 2021, 12:48 PM

#

Yes that's correct. Just pick the 8 questions to answer from the remaining 13-2=11

slow jewel Mar 27, 2021, 12:48 PM

#

what about part b?

weary tiger Mar 27, 2021, 12:54 PM

#

For the first question to answer, you have 2 possible choices: either question 1 or question 2. For the remaining 9 question to answer, you have 11C9 = 55 options

#

By the multiplication rule

#

,calc 2*55

vital dewBOT Mar 27, 2021, 12:55 PM

#

Result:

slow jewel Mar 27, 2021, 12:57 PM

#

i should have became a physicist

weary tiger Mar 27, 2021, 12:57 PM

#

Discrete maths is a pain for me too

slow jewel Mar 27, 2021, 12:58 PM

#

its just counting problems

weary tiger Mar 27, 2021, 12:58 PM

#

counting is hard

#

mniip

slow jewel Mar 27, 2021, 12:58 PM

#

seems easy for you

#

i have the answers, but i dont know how to get there lol

weary tiger Mar 27, 2021, 12:58 PM

#

no its just me facing such questions routinely

#

and i think i have your book

#

its called "combinatorics and graph theory"

#

no?

slow jewel Mar 27, 2021, 12:59 PM

#

#

it covers more than just graph theory and combinatorics

weary tiger Mar 27, 2021, 1:00 PM

#

nice one

#

have you covered any graph theory yet?

slow jewel Mar 27, 2021, 1:01 PM

#

yes

#

ive done graph thoery and difference equations

weary tiger Mar 27, 2021, 1:02 PM

#

same ^^ but I hard time with graph theory tbh

earnest dirge Mar 27, 2021, 3:29 PM

#

can someone help me with that ?

naive gulch Mar 27, 2021, 5:19 PM

#

#

How did they reach the $140/5n conclusion?

#

They say "at least $140" when the amount is a multiple of 5 but isn't $50 a multiple of 5?

tight lotus Mar 27, 2021, 5:21 PM

#

yes but $50 is less than $140

#

their conclusion only pertains to numbers >= 140
and divisible by 5

naive gulch Mar 27, 2021, 5:23 PM

#

tight lotus their conclusion only pertains to numbers >= 140 and divisible by 5

But where did that 140 come from? Like in my eyes I'm not understanding because it sounds arbitrary

#

I'm sure it isn't I just don't quite understand

tight lotus Mar 27, 2021, 5:32 PM

#

it's just the first number for which the pattern starts
I can't think of the equation atm :/

#

more importantly, they didn't use an equation;
they systematically wrote down reachable numbers from least to greatest and then *conjectured* just by looking at them that there is this pattern that starts at 140, in which the next number will be 5 greater

naive gulch Mar 27, 2021, 5:50 PM

#

Ooh

#

I see thank you!

naive gulch Mar 27, 2021, 6:06 PM

#

#

Here they pick n = 28 to n = 32 for their basis step

#

#

But then here they use k >=32

#

I'm sorta confused again, why didn't they just use 1-2 like n = 28 and n= 29 for basis, why all the way to 5?

#

nvm, I think thats literally part of strong induction

naive gulch Mar 27, 2021, 6:35 PM

#

Ah I finally see now

naive gulch Mar 27, 2021, 7:34 PM

#

#

#

Jesus, I know more practice will get me better intuition but I just don't have the thought process to get through induction steps sometimes

#

If I'm understanding this right, the first step is to break off a column so its one less column and the same rows represented by (m-1) * q, and then a 1 * q rectangle being a single column of the new break?

#

#

This is the part specifically I'm confused about then

naive gulch Mar 27, 2021, 7:58 PM

#

Where does the +1 come from in the (m-1)q -1 + (q-1) +1 come from? k+1?

errant bear Mar 28, 2021, 12:00 AM

#

yes

naive gulch Mar 28, 2021, 12:12 AM

#

errant bear yes

ah okay thanks!

#

#

Similarly then I get where this +1 comes from (although it confuses me since we already modified k+1 to k-2), but where does this +3 pop up from?

#

Wait

#

I get the +1, its from the 2^1

sturdy zodiac Mar 28, 2021, 12:13 AM

#

it's putting eveyrthing under a common denominator

naive gulch Mar 28, 2021, 12:13 AM

#

Oh

#

So 2^1 adds 1

#

and then 1/1 -> 3/3

#

?

sturdy zodiac Mar 28, 2021, 12:13 AM

#

like $\frac{k-2}{3} + 1 = \frac{k-2+3}{3}$

vital dewBOT Mar 28, 2021, 12:13 AM

#

young_smasher

sturdy zodiac Mar 28, 2021, 12:13 AM

#

yeah basically

naive gulch Mar 28, 2021, 12:14 AM

#

Ah ok thanks that makes sense

lethal prawn Mar 28, 2021, 12:15 AM

#

How many flags can we make with 7 stripes, if we have 2 white, 2 red, and 3 green
stripes? Justify.

naive gulch Mar 28, 2021, 12:16 AM

#

Induction is killing me I've done 5/16 of my problem set in a whopping 6 hours of working averaging over an hour per question

lethal prawn Mar 28, 2021, 12:16 AM

#

I feel like this is asking me to basically make a case where I subtract 1 from the stripe count each time I add a stripe to the flag.

#

Am I wrong?

naive gulch Mar 28, 2021, 1:12 AM

#

#

What is the intuition here for doing an-2 instead of an-1?

#

Like I get the problem and how it works later

errant bear Mar 28, 2021, 2:16 AM

#

because they are equal

weary tiger Mar 28, 2021, 1:20 PM

#

Hello, I'm new to coding theory and would appreciate some help. Let C and C' be two codes with check matrices H and H' respectively where H' is obtained from H by rearranging the columns of H in a certain why. Explain the relation between codewords in C and C'

#

In the previous question I was asked to find an example of H where C and C' are not the same

graceful vapor Mar 28, 2021, 6:02 PM

#

What methods am I going to use to prove this?

near prawn Mar 28, 2021, 6:04 PM

#

the hint is pretty useful

weary tiger Mar 28, 2021, 6:09 PM

#

Sure because if is even then n/2 is a number so that’s ez

graceful vapor Mar 28, 2021, 6:27 PM

#

maybe im thinking too much but do you do some kind of contrapositive proof for this? I feel like I'm missing something

weary tiger Mar 28, 2021, 6:29 PM

#

Just write out the odd case

#

what does it mean for a number to be odd

graceful vapor Mar 28, 2021, 6:32 PM

#

n doesn't divide evenly and the two numbers added are a difference of 1

weary tiger Mar 28, 2021, 6:33 PM

#

id rather say: there exists an integer k such that n=2k+1

graceful vapor Mar 28, 2021, 6:34 PM

#

oh yeah thats the proper way of saying it

#

so the floor of n/2 is equivalent to k?

graceful vapor Mar 28, 2021, 7:03 PM

#

okay i managed to figure it out

kind geode Mar 28, 2021, 7:14 PM

#

is it a fact that if u mod a number (n) by (m) that the possible outcome values will always be 0-(m-1)

Screen_Shot_2021-03-28_at_3.14.03_PM.png

errant bear Mar 28, 2021, 7:21 PM

#

yes

obtuse lance Mar 28, 2021, 7:26 PM

#

I don't think it's always implemented this way in programming languages for the record

fast umbra Mar 28, 2021, 7:28 PM

#

https://cdn.mathpix.com/snip/images/hgFhk1BfOmjZRK2G-W52T349MZnE5U0U7MOjR5-zZY4.original.fullsize.png did I prove it?

kind geode Mar 28, 2021, 7:43 PM

#

errant bear yes

ty

kind geode Mar 28, 2021, 7:43 PM

#

obtuse lance I don't think it's always implemented this way in programming languages for the ...

and yea very differenyt just in like discrete math ty tho

fast umbra Mar 28, 2021, 7:44 PM

#

fast umbra https://cdn.mathpix.com/snip/images/hgFhk1BfOmjZRK2G-W52T349MZnE5U0U7MOjR5-zZY4....

i feel like i lack something before i conclude

weary tiger Mar 29, 2021, 1:19 AM

#

@fast umbra your proof doesn't really make sense

normal sentinel Mar 29, 2021, 3:00 AM

#

what makes a set countable is onto functions? or both one-to-one AND onto?

weary tiger Mar 29, 2021, 3:01 AM

#

hommies is there a linear time algo for mst

naive gulch Mar 29, 2021, 3:31 AM

#

#

For B) I'm pretty rusty on combinations, I know since order matters its a lot

#

I was thinking like 6 + 5! but that sounds like too many, is it like division 6!/2! or smth? That doesn't sound right either argh

#

Wait is it even! Or is it counting? like for a) I wrote 6 + 5!, but is it just 6 + 5 + 4 + 3 + 2 + 1?

last timber Mar 29, 2021, 3:58 AM

#

is that rosen?

red wigeon Mar 29, 2021, 5:13 AM

#

how do you get from
1 (congruent=) 8(-4) mod 11
to
1 (congruent=) 8(7) mod 11 ?

#

im trying to find the multiplicitive inverse of 8 mod 11, so i used the extended euclidean algorithm on gcd(8,11)

#

i got -4, but it says the answer should be 7

#

im assuming theyre eq

#

oh

#

they just added 11 to it, didnt they

#

crazy how that works, sometimes the question only needs to leave your lips for you to understand what you did wrong

#

thanks

errant bear Mar 29, 2021, 5:19 AM

#

are u thanking urself

red wigeon Mar 29, 2021, 5:20 AM

#

uhhhhhh

#

yessss

#

also, i do have a question actually

#

when im doing this extended euclidean algorithm, trying to find the multiplicitive inverse, when i do it on 8 mod 11, it ends up being gcd(8, 11), and my first equation is 11 = 8*1 + 3.

at the end I get an equation

1 = 3 * 11 - 4 * 8
so the inverse i find is -4. does the 3 have a special meaning in this case? for example, is 3 the inverse of 11 or something?

errant bear Mar 29, 2021, 5:27 AM

#

11=0 so 3 cant be the inverse, as 11 doesnt have an inverse mod 11

red wigeon Mar 29, 2021, 5:27 AM

#

ahh shoot, i think i see

errant bear Mar 29, 2021, 5:27 AM

#

3 is just the number that happens to solve 11x + 8y = 1

patent reef Mar 29, 2021, 5:28 AM

#

Hey am interrupting?

red wigeon Mar 29, 2021, 5:28 AM

#

so for the euclidean algorithm gcd(8,11), we always take the bigger number on the left, like 11 = 8*1 + 3?

#

and thanks

errant bear Mar 29, 2021, 5:29 AM

#

i mean yeah, if you want to do it the other way it doesnt really matter

#

its just a lot more helpful to do it that way

red wigeon Mar 29, 2021, 5:31 AM

#

tyty

faint narwhal Mar 29, 2021, 5:41 AM

#

@errant bear thanks that helped a ton

#

@errant bear really appreciate it

errant bear Mar 29, 2021, 5:42 AM

#

please dont ping me @faint narwhal i am trying to sleep @faint narwhal .thanks

faint narwhal Mar 29, 2021, 5:42 AM

#

@errant bear oh sorry

#

@errant bear won't ping you again

errant bear Mar 29, 2021, 5:43 AM

#

i will let the moderation know if you keep doing this @faint narwhal . i do not tolerate this behaviour.

faint narwhal Mar 29, 2021, 5:43 AM

#

@errant bear i offer my deepest apologies

#

@errant bear I was only trying to express my appreciation

errant bear Mar 29, 2021, 5:44 AM

#

@moderation

#

help

#

hello? @moderation

#

i am trying to ping you @moderation

quaint star Mar 29, 2021, 5:44 AM

#

opencry

errant bear Mar 29, 2021, 5:45 AM

#

@quaint star can you please direct the moderation of this establishment to me. @faint narwhal is jesting and i am trying to sleep

quaint star Mar 29, 2021, 5:47 AM

#

I am moderation. If @faint narwhal didn't ping you @errant bear , how could @faint narwhal be sure that you @errant bear got their apology? Stop being a baby and put your phone on silence.

errant bear Mar 29, 2021, 5:48 AM

#

wow. i am offended at the lack of of respect and empathy in this serving by the moderation. if not even the moderation is willing to help me out with handling the joker @faint narwhal i do not know what is going to happen

quaint star Mar 29, 2021, 5:50 AM

#

Your offense has been noted, and the note will be thrown away.

errant bear Mar 29, 2021, 5:53 AM

#

wow. i now understand what kind of serving this is... i am a pauled.

last timber Mar 29, 2021, 6:50 AM

#

@errant bear good night

errant bear Mar 29, 2021, 7:04 AM

#

good morning @last timber i just woke up i feel well rested

#

🙂

last timber Mar 29, 2021, 7:05 AM

#

good morning @errant bear good to hear

errant bear Mar 29, 2021, 7:22 AM

#

i am always happy to share @faint narwhal

#

oh sorry @faint narwhal

#

i meant to ping @last timber

last timber Mar 29, 2021, 7:23 AM

#

@errant bear no problem

#

feel free to ping me @errant bear

errant bear Mar 29, 2021, 7:24 AM

#

okay i will keep that in mind szarekh, the silent king @last timber

edgy totem Mar 29, 2021, 7:59 AM

#

#

Stuck on qn 25 h)

stray reef Mar 29, 2021, 8:18 AM

#

@edgy totem you can write $x_2 = 5 + y_2$ and $x_3 = 10 + y_3$ and count the solutions of the equation $x_1 + y_2 + y_3 + x_4 + x_5 + x_6 = 25$ with $x_1, y_2, y_3 \leq 9$ and all variables nonnegative

vital dewBOT Mar 29, 2021, 8:18 AM

#

Ann

edgy totem Mar 29, 2021, 8:21 AM

#

how do you count the number of solutions to x_1+x_2...+x_6 where the restriction x<9 is only on 3 of the variables

stray reef Mar 29, 2021, 8:21 AM

#

edgy totem how do you count the number of solutions to x_1+x_2...+x_6 where the restriction...

inclusion-exclusion principle

edgy totem Mar 29, 2021, 8:22 AM

#

ahh okay

#

thank you

#

is it also equivalent to solving

#

nvm

#

wait

#

if x1,x2,x3 was less than 9

#

then 9 + 9+9+x4+x5+x6 > 25

#

and x4+x5+x6>-3.....

uncut matrix Mar 29, 2021, 8:56 AM

#

nevermind, I got it!

#

it was dumb by me

#

I need to double check more often

#

thank you!

fast umbra Mar 29, 2021, 9:31 AM

#

weary tiger <@!220222962123538432> your proof doesn't really make sense

Thought so 😦 how would you prove it?

fast umbra Mar 29, 2021, 9:50 AM

#

https://cdn.mathpix.com/snip/images/hgFhk1BfOmjZRK2G-W52T349MZnE5U0U7MOjR5-zZY4.original.fullsize.png

weary tiger Mar 29, 2021, 9:50 AM

#

Let x in f(CnD). Exists y in CnD s.t f(y)=x. By the definition of intersection y is in C and y is in D. So f(y)=x in f(C) and f(y)=x in f(D) so x in f(D) n f(C) so LHS subset of RHS

fast umbra Mar 29, 2021, 9:51 AM

#

LHS, RHS?

weary tiger Mar 29, 2021, 9:52 AM

#

left handside

fast umbra Mar 29, 2021, 9:52 AM

#

Ah, thank you!

fast umbra Mar 29, 2021, 1:29 PM

#

I rewrote it a bit

worthy patrol Mar 29, 2021, 1:37 PM

#

Need help w this question

#

prisma cypress Mar 29, 2021, 4:32 PM

#

uh... i could use some guidance on how to determine if K3 is a subgraph of this... (bleh i wish subscript or whatever was possible on discord)

embedded_image_1_c5603a22-f847-4757-b76c-7921da9f68d3_LpWvb5PrFLRSQqIvop7d.png

weary tiger Mar 29, 2021, 4:37 PM

#

K_3 is the complete graph on 3 vertices right?

prisma cypress Mar 29, 2021, 4:37 PM

#

i believe so

weary tiger Mar 29, 2021, 4:37 PM

#

So it's essentially a "triangle"

#

It clearly is a subgraph of the given graph

prisma cypress Mar 29, 2021, 4:38 PM

#

that doesn't help me really comprehend how which is what im needing guidance on since just started this material.. today

#

the k graphs confuse me

weary tiger Mar 29, 2021, 4:40 PM

#

Well, to show that K3 is a subgraph, you need to show that its vertex set is a subset of the vertex set of the "bigger" graph (the same applies for the edge set)

#

K3 given by ({1,3,5}, {13,15,35}) is a subgraph

last timber Mar 29, 2021, 4:42 PM

#

{13,15,35}

#

thonkzoom

prisma cypress Mar 29, 2021, 4:43 PM

#

i see...k4 might be one then..? but it described that as done either as a square or as a triangle with the dot in the middle.. unsure about how it is in the example graph

weary tiger Mar 29, 2021, 4:43 PM

#

last timber ```{13,15,35}```

it's a simplification for writing the edge set

prisma cypress Mar 29, 2021, 4:45 PM

#

... anyway moving on... now uh im not sure if this is possible but im being asked to either come up with a 3 regular graph with 5 vertices if it is.. same with a 3 regular graph with 6.. hm.

last timber Mar 29, 2021, 4:46 PM

#

prisma cypress Mar 29, 2021, 4:47 PM

#

...?

last timber Mar 29, 2021, 4:48 PM

#

anyway

#

k-regular graph with vertices DNE

weary tiger Mar 29, 2021, 4:48 PM

#

Have you heard of the "handshake lemma"?

#

It basically says that the sum of the degrees over all vertices in a given graph is equal to twice the number of edges

prisma cypress Mar 29, 2021, 4:50 PM

#

uh... there was a mention of some induction proof or theorem that stated degrees = 2 * number of edges but never heard of this "handshake lemma"

weary tiger Mar 29, 2021, 4:57 PM

#

You can use this lemma

#

3*5 = 15 which is not even

#

So a 3 regular graph on 5 vertices doesn't exist

prisma cypress Mar 29, 2021, 5:00 PM

#

so... a 3 regular one with 6 vertices could potentially exist but im not sure how i'd draw that if it did

weary tiger Mar 29, 2021, 5:00 PM

#

each vertex should have 3 neighbors

#

a 3-regular graph with 6 vertices is bipartite

#

put 3 vertices on one side and then 3 vertices on the other

#

then put an edge between each pair

last timber Mar 29, 2021, 5:02 PM

#

weary tiger Mar 29, 2021, 5:03 PM

#

That’s the simplest way to draw such a graph.

#

If it’s unlabelled, then two structures exist (up to isomorphism)

#

prisma cypress Mar 29, 2021, 5:05 PM

#

this is gonna be a weird chapter, i can tell already lol

weary tiger Mar 29, 2021, 5:06 PM

#

it's difficult to start with it

#

but you'll get the hang of it

prisma cypress Mar 29, 2021, 5:07 PM

#

okay... now this is one i definitely don't know how to do and im not seeing anything that spells it out in the section.. largest n such that kn = cn

last timber Mar 29, 2021, 5:08 PM

#

what are k and c

#

thonkzoom

#

oh you mean complete n-graph and n-cycle?

prisma cypress Mar 29, 2021, 5:08 PM

#

k is complete graph, c is cycle of vertices, according to book
a would be k and b would be c

last timber Mar 29, 2021, 5:09 PM

#

then n is pretty easy to find

prisma cypress Mar 29, 2021, 5:10 PM

#

okay... then how would i go about determining/finding that

last timber Mar 29, 2021, 5:11 PM

#

prisma cypress k is complete graph, c is cycle of vertices, according to book a would be k and ...

well look

#

this already suggests that n < 5

#

so you have only 4 possible nominees

weary tiger Mar 29, 2021, 5:11 PM

#

n = 3

last timber Mar 29, 2021, 5:11 PM

#

you could do this by brute force tbh

weary tiger Mar 29, 2021, 5:12 PM

#

its the same graph (pictorially)

prisma cypress Mar 29, 2021, 5:12 PM

#

last timber well look

i believe you misunderstood. those aren't related to the problem, it was just as an example of k and c. i have no graphs to go with for the one in question

last timber Mar 29, 2021, 5:12 PM

#

for different problems there may be different methods

weary tiger Mar 29, 2021, 5:13 PM

#

if they are the same, they have the same edge set and vertex set (up to isomorphism)

prisma cypress Mar 29, 2021, 5:13 PM

#

let me put it another way then. this is all i have to go off of

last timber Mar 29, 2021, 5:13 PM

#

we already gave you an answer

#

for this particular problem

prisma cypress Mar 29, 2021, 10:05 PM

#

... does it matter which vertices from graph g i set c and e equal to? can't figure out which should correspond to 1 and which should correspond to 4

naive gulch Mar 30, 2021, 12:02 AM

#

For this Q I gotta use power set cardinality right?

#

Its subsets total - subsets < 1 to find subsets > 1, no?

minor dagger Mar 30, 2021, 12:04 AM

#

there would only be one subset with less than one element

#

it should be total subsets - subsets with cardinality < 2

thorn brook Mar 30, 2021, 2:58 AM

#

Hii

#

I need a lil hlp with maths induction

plucky thunder Mar 30, 2021, 4:16 AM

#

hi, i was wondering if this would be an example of an bipartite graph?

faint narwhal Mar 30, 2021, 4:19 AM

#

what do you think?

proven shard Mar 30, 2021, 4:22 AM

#

You need to partition the verticies

plucky thunder Mar 30, 2021, 4:22 AM

#

i did, but it comes back to the same part of the veritcies

#

so when i did V1 as {A, B, C} and V2 as {D, E, F}

#

an example would be A and C would match to each other, which im confused it its allowed

faint narwhal Mar 30, 2021, 4:23 AM

#

do you know what being bipartite means?

plucky thunder Mar 30, 2021, 4:24 AM

#

does it mean that it is made in 2 parts?

#

or has 2 parts to it?

faint narwhal Mar 30, 2021, 4:24 AM

#

you should go figure out exactly what bipartite means

plucky thunder Mar 30, 2021, 4:25 AM

#

it says that every edge should connect to a vertex according to my notes and textbook

faint narwhal Mar 30, 2021, 4:26 AM

#

that doesn't make any sense

#

all edges connect vertices

plucky thunder Mar 30, 2021, 4:26 AM

#

yea im really confused on how it works anyways beside for the partion part of the graph

faint narwhal Mar 30, 2021, 4:26 AM

#

you should go figure out what bipartite actually means

errant bear Mar 30, 2021, 5:48 AM

#

@faint narwhal wow thanks for the help! i now know that i should go figure out what bipartite means. thanks 🙂

#

you're an excellent helper 🙂 @faint narwhal

prisma cypress Mar 30, 2021, 11:33 AM

#

... i can't tell if zopherus is ever being serious

gritty crescent Mar 30, 2021, 2:10 PM

#

sully

pale epoch Mar 30, 2021, 2:26 PM

#

||this is unironically the best way anyone could have helped with this question||

sand cipher Mar 30, 2021, 7:46 PM

#

need help with this practice question

stray reef Mar 30, 2021, 7:48 PM

#

there are four questions here.

#

which one do you need help on?

#

@sand cipher

sand cipher Mar 30, 2021, 7:53 PM

#

well all of them

#

he does not give a problem this hard in class but the practice problem is this hard

#

so i'm lost

stray reef Mar 30, 2021, 7:54 PM

#

okay i don't have time to help with all of these

#

sorry

sand cipher Mar 30, 2021, 7:55 PM

#

could u help with just the first

#

i'm honestly most scared of first and third

stray reef Mar 30, 2021, 7:58 PM

#

you'll have to show some progress

#

otherwise i'll just go to sleep

sand cipher Mar 30, 2021, 8:07 PM

#

well ik that all of that $n!=1\cdot2\cdot3\cdots n$

vital dewBOT Mar 30, 2021, 8:07 PM

#

Centrous

sand cipher Mar 30, 2021, 8:07 PM

#

and that all of the term are less then n

#

using induction

clear apex Mar 31, 2021, 12:49 AM

#

can someone help me 🧎🏻‍♀️

#

kind geode Mar 31, 2021, 1:13 AM

#

the union of the natural numbers and positive rational is countable r ight?

weary tiger Mar 31, 2021, 1:17 AM

#

every countable union of countable sets is countable

kind geode Mar 31, 2021, 1:35 AM

#

okok thank you

wooden acorn Mar 31, 2021, 4:05 AM

#

Is there something similar to generating functions, but not generating functions? Like is there another way to encode information besides exponents?

#

I’ll probably spend some sitting time thinking about this tomorrow

unreal stump Mar 31, 2021, 4:06 AM

#

That would still be a generating function

#

Also see Dirichlet generating functions

#

https://en.m.wikipedia.org/wiki/Dirichlet_series

Dirichlet series

In mathematics, a Dirichlet series is any series of the form

...

#

You encode a series ($a_n$) as
\newline
$F(s)=\sum_{i=1}^{\infty} \frac{a_i}{i^s}$

vital dewBOT Mar 31, 2021, 4:10 AM

#

Drunknarwhal

faint narwhal Mar 31, 2021, 4:14 AM

#

Exponential generating functions too maybe?

wooden acorn Mar 31, 2021, 4:43 PM

#

Oh cool thanks

weary tiger Mar 31, 2021, 5:04 PM

#

Prove that there exists no graph with 2, 3, 4 or 5 vertices such that its only automorphism is the identity.

#

i'm not quite sure how to go about... induction seems rather daunting

#

and so does manually checking thonk

proven shard Mar 31, 2021, 5:27 PM

#

Prove that you only need to consider connected graphs
Draw all the connected graphs on 2,3,4,5 verticies and observe their nontrivial automorphisms

weary tiger Mar 31, 2021, 5:29 PM

#

clear apex

360 + (360 x 15%)

weary tiger Mar 31, 2021, 6:32 PM

#

if I have say the numbers 1 , 2 ,3 ,4 ... till 25
and I ask you to find all the primes between them
so the theorem says you first cross 2 cause 2 is prime right?
and then you cross every multiple of 2 ( crossing meaning you eliminate them, cz they are not prime )
but the theorem says every number from 2 till 2^2 that weren't crossed are primes
and I am asking why
I didn't understand why

unreal stump Mar 31, 2021, 6:36 PM

#

It doesn't say that

#

What theorem are you referring to?

weary tiger Mar 31, 2021, 6:38 PM

#

coral raven Mar 31, 2021, 6:40 PM

#

if the only prime you know is 2, then everything that doesn't divide by 2 up to ^2 is a new prime

#

so just 3 really

#

if the only primes you know are 2 and 3, then everything that doesn't divide by 2 or 3 up to 3^2 is a new prime

weary tiger Mar 31, 2021, 6:41 PM

#

I am gonna add to this that everything that doesn't divide 2 between 2 and 2^2

coral raven Mar 31, 2021, 6:41 PM

#

ok so it's because it's like

weary tiger Mar 31, 2021, 6:42 PM

#

coral raven if the only primes you know are 2 and 3, then everything that doesn't divide by ...

why up to 3^2

coral raven Mar 31, 2021, 6:42 PM

#

if you have a number n

#

and it divides by a prime p

#

where n > p > sqrt(n)

#

then you know it divides by at least one more prime q < sqrt(n)

weary tiger Mar 31, 2021, 6:43 PM

#

yes this I understand it

coral raven Mar 31, 2021, 6:43 PM

#

yeah so that's it isn't it

weary tiger Mar 31, 2021, 6:43 PM

#

p<sqrt(n)

coral raven Mar 31, 2021, 6:43 PM

#

so up to 49, if it doesn't divide by 2, 3 or 5 then it's prime

#

up to 121, if it doesn't divide by 2, 3, 5 or 7 then it's prime

weary tiger Mar 31, 2021, 6:43 PM

#

hold on hold on

#

1 by 1

#

so A prime factor of n can only be up to sqrt(n)

coral raven Mar 31, 2021, 6:44 PM

#

no

weary tiger Mar 31, 2021, 6:44 PM

#

what?

coral raven Mar 31, 2021, 6:44 PM

#

if n isn't prime, then the smallest prime factor of n is at most sqrt(n)

#

there might be another one

#

so take 10

#

5 is a prime factor of 10

#

but sqrt(10) < 5

#

so 10 < 5^2

weary tiger Mar 31, 2021, 6:45 PM

#

ah

coral raven Mar 31, 2021, 6:45 PM

#

so 5 can't be the smallest prime factor of 10, because the smallest number with only 5 as its factors is 25, apart from 5

weary tiger Mar 31, 2021, 6:45 PM

#

then where does the theorem that says a prime factor of a number must always be less than sqrt of n?

coral raven Mar 31, 2021, 6:45 PM

#

no

#

the smallest prime factor

weary tiger Mar 31, 2021, 6:46 PM

#

ah the smallest prime factor

coral raven Mar 31, 2021, 6:46 PM

#

of a non-prime

weary tiger Mar 31, 2021, 6:46 PM

#

ah

coral raven Mar 31, 2021, 6:46 PM

#

ok so it's like

#

right, starting over, i'm messing up this explanation

#

so say n is not prime and it has a prime factor p > sqrt(n)

weary tiger Mar 31, 2021, 6:46 PM

#

coral raven so 5 can't be the smallest prime factor of 10, because the smallest number with ...

this I dont understand

coral raven Mar 31, 2021, 6:46 PM

#

say n is not prime and it has a factor p > sqrt(n), eg. n is 10 and p is 5 > sqrt(10)

weary tiger Mar 31, 2021, 6:47 PM

#

coral raven so say n is not prime and it has a prime factor p > sqrt(n)

alright so p is the smallest prime factor here or considered like that

coral raven Mar 31, 2021, 6:47 PM

#

no

#

lemme type it all out in one go

weary tiger Mar 31, 2021, 6:47 PM

#

alright I will shutup sorry

coral raven Mar 31, 2021, 6:53 PM

#

ok so i was typing out a really long thing but i thought of a shorter explanation

#

if n = kp and p > sqrt(n), then k < sqrt(n)

k must either be a prime or have even smaller prime factors

either way there is a prime factor < sqrt(n)

and essentially if you know all the primes < sqrt(n), then you don't need to consider any primes p between sqrt(n) and n, because if you have any p > sqrt(n), then you know that there's a smaller prime goes into n

weary tiger Mar 31, 2021, 6:55 PM

#

yes understood

#

what you said now I understood it

#

ok continue

coral raven Mar 31, 2021, 6:57 PM

#

no, that's it

weary tiger Mar 31, 2021, 6:58 PM

#

lets clarify more

coral raven Mar 31, 2021, 6:58 PM

#

ok

weary tiger Mar 31, 2021, 6:58 PM

#

any number has a prime factor > sqrt(n)?

#

any non prime

#

say 12

coral raven Mar 31, 2021, 6:59 PM

#

no

weary tiger Mar 31, 2021, 6:59 PM

#

so it depends right?

coral raven Mar 31, 2021, 6:59 PM

#

any non-prime, or composite, number has a prime factor =< sqrt(n)

#

but for example 8 has no prime factors > sqrt(8)

weary tiger Mar 31, 2021, 6:59 PM

#

yeah alright true

#

ok now going back to the theorem

#

if you have say 3 which is prime and you crossed all multiples of 2 and 3

#

now I still don't see why the numbers that weren't crossed between 3 and 3*3 are prime

#

(I understood everything you said earlier)

coral raven Mar 31, 2021, 7:01 PM

#

if you know all the primes =< sqrt(n)

#

then if n is composite and has a prime factor > sqrt(n)

#

it also has to have a prime factor =< sqrt(n)

#

so if it doesn't have any prime factors =< sqrt(n)

#

it has no prime factors > sqrt(n) either

#

except itself

weary tiger Mar 31, 2021, 7:02 PM

#

just to clarify n is the composite number or the non prime number

#

or the potential prime number

coral raven Mar 31, 2021, 7:02 PM

#

potential

weary tiger Mar 31, 2021, 7:03 PM

#

coral raven then if n is composite and has a prime factor > sqrt(n)

you said not all numbers have prime factor > sqrt(n)

coral raven Mar 31, 2021, 7:03 PM

#

yes

#

but if it does

#

then it also has something =< sqrt(n)

#

so if you've checked everything =< sqrt(n)

#

there's no point checking > sqrt(n)

weary tiger Mar 31, 2021, 7:04 PM

#

but here you are talking in reverse

coral raven Mar 31, 2021, 7:04 PM

#

yes

weary tiger Mar 31, 2021, 7:04 PM

#

here you are saying find the prime factors of a number

#

I am speaking in reverse

coral raven Mar 31, 2021, 7:04 PM

#

ok so just logic: so suppose whenever you have A, you have B

#

then if you don't have B

#

you definitely don't have A

#

right?

weary tiger Mar 31, 2021, 7:05 PM

#

I understood what you said you said if we don't have a prime factor for a number between 1 and sqrt(number) then the number is prime

#

but my question is in reverse

coral raven Mar 31, 2021, 7:05 PM

#

no wait

#

go back to the logic

#

if you always have B whenever you have A: then if you see you don't have B, you know you don't have A, right?

weary tiger Mar 31, 2021, 7:06 PM

#

uh sorry what do you mean by a and b

coral raven Mar 31, 2021, 7:06 PM

#

logic

weary tiger Mar 31, 2021, 7:06 PM

#

A implies B?

coral raven Mar 31, 2021, 7:06 PM

#

yes

#

if A implies B

#

then not-B implies not-A

weary tiger Mar 31, 2021, 7:06 PM

#

A is finding a prime less than sqrt n?

coral raven Mar 31, 2021, 7:06 PM

#

no

#

ok so

weary tiger Mar 31, 2021, 7:06 PM

#

what is A then?

coral raven Mar 31, 2021, 7:08 PM

#

whenever you have A, you have B
then if you don't have B
you definitely don't have A

whenever n is not prime and you have a prime factor > sqrt(n), you have a prime factor =< sqrt(n)
so if you think n is not prime but you don't have a prime factor =< sqrt(n), you don't have a prime factor > sqrt(n)
so n has to be prime

weary tiger Mar 31, 2021, 7:09 PM

#

ah

#

@coral raven but I swear how does that relate to n being between his primefactor and hisprimefactor^2

coral raven Mar 31, 2021, 7:13 PM

#

so if you know all the prime factors =< sqrt(n), then all the composite numbers up to n have one of those prime factors
so if you know all the prime factors =< m, then all the composite numbers up to m^2 have one of those prime factors