I forget how we found this problem | Mathematics | Page 2

cunning stump Sep 28, 2024, 11:08 AM

#

I think im done

cunning stump Sep 28, 2024, 11:08 AM

#

cunning stump I think im done

I didnt do it

#

But im rage quiting

#

I tried taking the list of tables and just like remove duplicates but its now even bigger number

#

If im coding ever again it will be in a purely functional programming lang

tough kettle Sep 28, 2024, 11:26 AM

#

noo

tough kettle Sep 28, 2024, 11:26 AM

#

cunning stump If im coding ever again it will be in a purely functional programming lang

LOLLLLLLLL

cunning stump Sep 28, 2024, 11:30 AM

#

My code found 563 unique combinations for f(5 , 5)

#

I dont know how

#

I removed all duplicates and i dont think my code can give wrong combintions

#

I would have to code now a program that takes a combination , validates it ,and ....

#

@tough kettle is there some part of your code that takes a combination and gives like True if it really is and false if it isnt

#

Or like do you have that

tough kettle Sep 28, 2024, 11:33 AM

#

yeah

#

except its bad

cunning stump Sep 28, 2024, 11:33 AM

#

It can be slow it would be really helpfull to debug my program with that

tough kettle Sep 28, 2024, 11:33 AM

#

it doesn't work

#

well it doesn't work in c

#

i think it works in python

#

you generate some bitmasks and do some bitwise ops

#

f.py is somewhere up there

cunning stump Sep 28, 2024, 11:34 AM

#

Whats the input?

subtle lake Sep 28, 2024, 11:34 AM

#

i'm working on my algorithm rn

tough kettle Sep 28, 2024, 11:35 AM

#

cunning stump Whats the input?

do you have f.py?

#

ok the thing inside the if inside the nested loops validates stuff

cunning stump Sep 28, 2024, 11:35 AM

#

No but im asking what kind of structure does it take

tough kettle Sep 28, 2024, 11:36 AM

#

g is an int which represents a binary grid

#

so like

cunning stump Sep 28, 2024, 11:36 AM

#

My table is basically a list of white cells

tough kettle Sep 28, 2024, 11:36 AM

#

ah

#

ok

#

uh

#

so like

cunning stump Sep 28, 2024, 11:36 AM

#

[(X_1 , Y_1) , (X_2 , Y_2) ... ]

#

Where those are white cells

#

Saves on memory ig

tough kettle Sep 28, 2024, 11:37 AM

#

lets say g is 0b10010110100101110, m is 4, n is 4
so the grid here is 1001 \n 0110 \n 1001 \n 0110

#

this is how my program achieves its speed lol

#

the 1s are white cells, the 0s are black cells

cunning stump Sep 28, 2024, 11:38 AM

#

Hmm i think for my case i will just like write a loop that loops through whole table

#

And just does a check if any whites can be placed

#

It should be all false

tough kettle Sep 28, 2024, 11:46 AM

#

i'll replace it with my code when you send it

#

to make it faster

cunning stump Sep 28, 2024, 12:10 PM

#

Ok i found the extra ones

#

They are just wrong

#

The new problem now is that without those extra ones my program undercounts

#

For every larger n im just fixing my code

#

Thats how many flaws it has

#

First it did f(3 , 3) wrong and i fixed it. Then it did f(4 , 4) and i fixed it now f(5 , 5) is wrong

#

Im kind of asking myself is my algorithm even consistent or will i have to fix it for every laeger n

#

Oh i see the problem

#

#

I thought that this cell was always safe in my algorithm

#

So i didnt bother to check if white cell can be placed there

#

I think thats the last flaw in my algorithm

#

Ok i should prob rewrite my whole algorithm because its getting ugly

#

This problem has given me nothing other than pain and suffering

subtle lake Sep 28, 2024, 12:27 PM

#

bearlain

cunning stump Sep 28, 2024, 12:29 PM

#

If my algorithm isnt polynomial time then this wasnt worth it

#

I mean on paper it souns fast. As everything you do will be to get a combination so there is no extra checking stuff

subtle lake Sep 28, 2024, 12:39 PM

#

so it's supposed to be O(however many grids there are)?

cunning stump Sep 28, 2024, 12:44 PM

#

Well it would seem to me that it would be something like that but idk in practice how would you calculate big O of that algo

#

I mean there are more operations done

subtle lake Sep 28, 2024, 12:45 PM

#

that doesn't seem very fast on paper to me

cunning stump Sep 28, 2024, 12:45 PM

#

I mean it is how a human would manually calculate this

subtle lake Sep 28, 2024, 12:46 PM

#

i wouldn't

cunning stump Sep 28, 2024, 12:46 PM

#

How would you?

subtle lake Sep 28, 2024, 12:46 PM

#

the same way my algorithm does (which i've just been mysteriously mentioning a lot because i'm not sure if people want it spoiled yet)

cunning stump Sep 28, 2024, 12:47 PM

#

Ok well imma try and finish this

tough kettle Sep 28, 2024, 1:13 PM

#

ok

#

lets see

#

woah the sync is crazy

cunning stump Sep 28, 2024, 1:13 PM

#

My program is undercounting....

#

Again

#

How do i see a difference between 2 lists?

subtle lake Sep 28, 2024, 1:15 PM

#

difference in what way?

cunning stump Sep 28, 2024, 1:15 PM

#

Like [1 , 2 ,3 , 4] and [1 , 2 ,3] it would be [4]

subtle lake Sep 28, 2024, 1:16 PM

#

python?

cunning stump Sep 28, 2024, 1:16 PM

#

Yes

subtle lake Sep 28, 2024, 1:16 PM

#

you could make them sets and set difference

#

might lose some information like the order though

#

and like if you want [1 , 2 , 3 , 3, 4] and [1 , 2 ,3] to return [3, 4] then that wouldn't work ofc

#

you could use Counter if you wanted that ig

cunning stump Sep 28, 2024, 1:23 PM

#

subtle lake you could make them sets and set difference

Will try that prob

cunning stump Sep 28, 2024, 1:23 PM

#

subtle lake might lose some information like the order though

Even better

#

My algorithm has so many edge cased

#

I did it

#

It works

subtle lake Sep 28, 2024, 1:34 PM

#

awoo

cunning stump Sep 28, 2024, 1:34 PM

#

Damn this solved 7x7 in seconds and im on my phone

subtle lake Sep 28, 2024, 1:35 PM

#

coding on your phone?

#

damn

cunning stump Sep 28, 2024, 1:36 PM

#

subtle lake coding on your phone?

I like it more for scripting

#

Like i code on a computer only when its multiple file project

#

Like svelte or something like that

#

https://pastebin.com/6XVcrHCx

Can anyone speed test

Pastebin

def algorithm(n , cell , table): if cell is True: return 1 next_...

Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.

#

Idk how

subtle lake Sep 28, 2024, 1:39 PM

#

cunning stump Sep 28, 2024, 1:40 PM

#

That.... is slow right?

subtle lake Sep 28, 2024, 1:40 PM

#

yes

#

my algorithm

cunning stump Sep 28, 2024, 1:41 PM

#

Is it also written in python?

subtle lake Sep 28, 2024, 1:41 PM

#

yea

#

i just ran both of them in separate jupyter notebook cells in the same file

cunning stump Sep 28, 2024, 1:42 PM

#

Well my time wasnt that well spent then ig

subtle lake Sep 28, 2024, 1:43 PM

#

wasn't spent too terribly

#

got something out of it

cunning stump Sep 28, 2024, 1:44 PM

#

Is your algorithm pure python or like uses alot of functions from C?

subtle lake Sep 28, 2024, 1:44 PM

#

but yea at least one operation for each valid grid is not going to be pretty limiting

#

just python

#

just simple python objects, no numpy or anything

cunning stump Sep 28, 2024, 1:45 PM

#

Thats cool

#

I mean how does your algorithm scale

#

What about f(9 , 9) or something like thaz

subtle lake Sep 28, 2024, 1:48 PM

#

f(n+1, n+1) takes about 3x as long as f(n,n). but f(2n,n) only takes (about) twice as long as f(n,n)

#

so as long as min(m,n) isn't too big, one of the numbers can go really high

#

like f(5,10^6) for example i've computed

cunning stump Sep 28, 2024, 1:49 PM

#

So like f(n , n) has big O of 3^n?

subtle lake Sep 28, 2024, 1:50 PM

#

yea

cunning stump Sep 28, 2024, 1:51 PM

#

I dont really know what big O of my algo should be

#

Imma ask chat gpt

subtle lake Sep 28, 2024, 1:51 PM

#

i believe it is exponential

#

in mn

cunning stump Sep 28, 2024, 1:52 PM

#

But im not checking every combination

#

Im only checking every combination that makes sense

#

Aka every combination that will give me a solution

subtle lake Sep 28, 2024, 1:54 PM

#

#

#

predictions on f(8,8)?

cunning stump Sep 28, 2024, 1:56 PM

#

Like few minutes ig

#

Or even hours

subtle lake Sep 28, 2024, 2:00 PM

#

cunning stump Aka every combination that will give me a solution

but the number of valid grids still grows fast

#

cunning stump Sep 28, 2024, 2:01 PM

#

Well yes

#

I would say my algorithm is polynomial in that

subtle lake Sep 28, 2024, 2:01 PM

#

polynomial in what?

cunning stump Sep 28, 2024, 2:01 PM

#

And due to that being exponential then it probably also is

cunning stump Sep 28, 2024, 2:02 PM

#

subtle lake polynomial in what?

Number of combinations

#

Like f(n , n)^6

subtle lake Sep 28, 2024, 2:02 PM

#

not constant?

#

yea you're cooked

subtle lake Sep 28, 2024, 2:04 PM

#

subtle lake

f(n+1,n+1) is at least 2*f(n,n) so that's already at least exponential for your algorithm

#

but it's much worse than that message makes it sound because the multiplier is much bigger than 2 (and grows)

cunning stump Sep 28, 2024, 2:04 PM

#

Or maybe more like f(n , n) *n^6

subtle lake Sep 28, 2024, 2:06 PM

#

f(8,8) still hasn't finished and i need to leave my computer

cunning stump Sep 28, 2024, 2:07 PM

#

subtle lake f(8,8) still hasn't finished and i need to leave my computer

Yeah expected

#

Whats max you computed?

subtle lake Sep 28, 2024, 2:09 PM

#

with my algorithm?

cunning stump Sep 28, 2024, 2:10 PM

#

Yes

#

f(n , n) not f(n , m)

subtle lake Sep 28, 2024, 2:10 PM

#

i don't think i've bothered going higher than 15

#

i could tell you f(19,19) but it would have to be later today joyspin

cunning stump Sep 28, 2024, 2:10 PM

#

So you got to 15. In how much time?

subtle lake Sep 28, 2024, 2:11 PM

#

like 4 minutes probably?

subtle lake Sep 28, 2024, 2:12 PM

#

subtle lake i could tell you f(19,19) but it would have to be later today <a:joyspin:6906302...

i will compute this btw just for fun

#

and because it's past the oeis page

cunning stump Sep 28, 2024, 2:12 PM

#

subtle lake like 4 minutes probably?

Damn...

subtle lake Sep 28, 2024, 2:14 PM

#

i gtg away from my computer for a while

#

i'll post what f(19,19) is sometime later

tough kettle Sep 28, 2024, 2:31 PM

#

@cunning stump hows your algorithm going

#

oh wow

#

nice

#

now its time to turn it into c

cunning stump Sep 28, 2024, 2:49 PM

#

subtle lake like 4 minutes probably?

How is that even possible? It would take a supercomputer 1 day to permorfm ammount the number of calculations that is the solutions.

#

Im guessing previous calculated f(n , n) would be given as an input?

subtle lake Sep 28, 2024, 2:51 PM

#

i don’t go through them all

#

and no i don’t use f(n-1,n-1) to assist in computing f(n,n)

cunning stump Sep 28, 2024, 2:52 PM

#

So basically magic

subtle lake Sep 28, 2024, 2:52 PM

#

pretty much

cunning stump Sep 28, 2024, 2:53 PM

#

Are you like calculating some other sequence and then getting this sequence in terms of that?

subtle lake Sep 28, 2024, 2:54 PM

#

it shouldn’t be that unbelievable though. to count the subsets of a size 100 set that are size 50 you don’t need to go through all 2^100 sets and check their size

cunning stump Sep 28, 2024, 2:56 PM

#

So is your algorithm like lego pieces and then you just connect them?

subtle lake Sep 28, 2024, 2:56 PM

#

kinda

subtle lake Sep 28, 2024, 2:56 PM

#

cunning stump Are you like calculating some other sequence and then getting this sequence in t...

not really

#

this is like 20 questions 😂

cunning stump Sep 28, 2024, 2:59 PM

#

I mean it looks like you arent actually calculting every solution. But rather something else and then number of solutions is in terms of that thing.

subtle lake Sep 28, 2024, 3:00 PM

#

there are sequences involved but that’s not really the main idea. they just happen to be made along the way

cunning stump Sep 28, 2024, 3:03 PM

#

I mean by https://sequencedb.net/s/A288956

#

This sequence can be written in terms of other sequences

#

Which may be easier to compute

subtle lake Sep 28, 2024, 3:04 PM

#

what exactly are you referring to?

#

well in any case i didn’t do anything related to anything on that page

#

but that is interesting hmmge

#

Inverse of 1334th cyclotomic polynomial.

#

wtf

twilit seal Sep 28, 2024, 3:10 PM

#

name drop for why

#

ummm no

rapid ravine Sep 28, 2024, 3:10 PM

#

twilit seal ummm no

maam

#

u literally called yourself "no one"

#

in the sense that u said if someone looks you in the eyes they'll have "nothing" staring back at them

#

that implies self deprecation in the sense that you're nothing

cunning stump Sep 28, 2024, 3:11 PM

#

subtle lake but that is interesting <:hmmge:1153028294552342579>

Instead of f(n , n)

#

You compute $$F\left( \sum_{k = 1}^n (4k ) + 1\right)$$

dapper wedgeBOT Sep 28, 2024, 3:12 PM

#

Pluton

cunning stump Sep 28, 2024, 3:12 PM

#

Of this

#

https://oeis.org/A332347

subtle lake Sep 28, 2024, 3:13 PM

#

i didn’t do that but now i’m sad i won’t be at my computer for a while because i want to see how high i can go with that

cunning stump Sep 28, 2024, 3:14 PM

#

What even is that seq

rapid ravine Sep 28, 2024, 3:14 PM

#

i love it when i see people that are smarter when it comes to maths then me

cunning stump Sep 28, 2024, 3:14 PM

#

"Array read by antidiagonals: T(m,n) is the number of maximal independent sets in the m X n king graph."

rapid ravine Sep 28, 2024, 3:14 PM

#

so many weird english words to discover

subtle lake Sep 28, 2024, 3:15 PM

#

cunning stump What even is that seq

it’s just this table https://oeis.org/A332347

#

but in a sequence

cunning stump Sep 28, 2024, 3:18 PM

#

Oh

#

Oh so its useless

subtle lake Sep 28, 2024, 3:20 PM

#

i may be able to abuse it

cunning stump Sep 28, 2024, 3:20 PM

#

How?

#

Its basically just says hey f(n , n) is on f(n , m) when n = m

subtle lake Sep 28, 2024, 3:21 PM

#

ah

#

i misread it

twilit seal Sep 28, 2024, 3:21 PM

#

rapid ravine in the sense that u said if someone looks you in the eyes they'll have "nothing"...

yea

subtle lake Sep 28, 2024, 3:22 PM

#

then yea that’s useless lol

twilit seal Sep 28, 2024, 3:22 PM

#

thats not self deprecating

rapid ravine Sep 28, 2024, 3:22 PM

#

elaborate

twilit seal Sep 28, 2024, 3:22 PM

#

i know my worth .

rapid ravine Sep 28, 2024, 3:22 PM

#

your worth is nothing then

twilit seal Sep 28, 2024, 3:22 PM

#

Take that back

rapid ravine Sep 28, 2024, 3:22 PM

#

or do u mean it in a more uh

#

maam it was a question

twilit seal Sep 28, 2024, 3:22 PM

#

im joking haha

rapid ravine Sep 28, 2024, 3:22 PM

#

not affirming anything

twilit seal Sep 28, 2024, 3:22 PM

#

im kinda busy atm

#

ill get back yo u

rapid ravine Sep 28, 2024, 3:23 PM

#

either way maybe u meant it in a more "I won't give you attention" way

#

like u wont look back at the person, i dunno

rapid ravine Sep 28, 2024, 3:23 PM

#

twilit seal ill get back yo u

ok

cunning stump Sep 28, 2024, 3:24 PM

#

It seems like the lcm one could be useful

subtle lake Sep 28, 2024, 3:24 PM

#

cunning stump Its basically just says hey f(n , n) is on f(n , m) when n = m

maybe. i do fear now that they all do this though

#

just in convoluted ways

cunning stump Sep 28, 2024, 3:24 PM

#

a(n)=lcm(A015343(n), A332347(A001844(n)))

#

Like if A001844(n) is less than sum of 4n + 1

#

Then it should be easier to compute maybe

#

And if A015343(n) is easier to compute

cunning stump Sep 28, 2024, 3:27 PM

#

subtle lake maybe. i do fear now that they all do this though

Yeah but like that one says f(n ,n ) is on f(n , m) this one says f(n , n) has some connection with f(n , m)

rapid ravine Sep 28, 2024, 3:27 PM

#

unrelated but i found this funni

cunning stump Sep 28, 2024, 3:27 PM

#

And maybe possibly f(n , m) that is easier to compute than f(n , n)

subtle lake Sep 28, 2024, 3:27 PM

#

my hopes are not very high

cunning stump Sep 28, 2024, 3:29 PM

#

You have to compute A332347(2n(n + 1) + 1)

#

Now just because its a big number doesnt mean its hard to compute

subtle lake Sep 28, 2024, 3:31 PM

#

what pairs (m,n) do those correspond to?

cunning stump Sep 28, 2024, 3:31 PM

#

It could be f(2 , m) as far as we know

cunning stump Sep 28, 2024, 3:31 PM

#

subtle lake what pairs (m,n) do those correspond to?

Wouldnt know

#

Wont be that hard to get i think

lunar shoal Sep 28, 2024, 3:33 PM

#

I sorted forum by recent and found this huge thread

#

did you find the algorithm yet?

subtle lake Sep 28, 2024, 3:34 PM

#

i wouldn’t say that

#

but also welcome waves

lunar shoal Sep 28, 2024, 3:35 PM

#

problem seems fun, i'll think about it

subtle lake Sep 28, 2024, 3:36 PM

#

yea i’ve had a lot of fun with it

cunning stump Sep 28, 2024, 3:37 PM

#

subtle lake what pairs (m,n) do those correspond to?

It coressponds to (n , n)

subtle lake Sep 28, 2024, 3:37 PM

#

lol rip

cunning stump Sep 28, 2024, 3:38 PM

#

2n(n + 1) + 1 is the sum of 4n + 1

#

What is lcm doing?

subtle lake Sep 28, 2024, 3:38 PM

#

subtle lake just in convoluted ways

so this was probably right

cunning stump Sep 28, 2024, 3:38 PM

#

I guess its saying that the random thing divides that number

cunning stump Sep 28, 2024, 3:38 PM

#

subtle lake so this was probably right

Yea

#

https://oeis.org/search?q=A015343&go=Search

#

Im confused

subtle lake Sep 28, 2024, 3:39 PM

#

the fact that they all used the array read by anti-diagonals and that already has the sequence we want embedded inside it was sus

cunning stump Sep 28, 2024, 3:40 PM

#

Yeah

subtle lake Sep 28, 2024, 3:40 PM

#

easy to just grab the (n,n) parts out of it

subtle lake Sep 28, 2024, 3:41 PM

#

cunning stump https://oeis.org/search?q=A015343&go=Search

lol. so taking lcm with 1 or -1 did nothing

cunning stump Sep 28, 2024, 3:42 PM

#

But its 0 sometimes

subtle lake Sep 28, 2024, 3:42 PM

#

not before 18 or whatever

cunning stump Sep 28, 2024, 3:42 PM

#

And lcm( 0 , x) ....

#

Oh yeah

#

Does it mean a_(19) is undefined blobwg

#

Makes no sense ik

subtle lake Sep 28, 2024, 3:43 PM

#

hmmge

cunning stump Sep 28, 2024, 3:43 PM

#

A finite grid with non finite ammount of combinations

subtle lake Sep 28, 2024, 3:45 PM

#

it means we can scrap that because it’s just coincidence

cunning stump Sep 28, 2024, 3:46 PM

#

Also https://oeis.org/A332347/b332347.txt

#

It looks cool

subtle lake Sep 28, 2024, 3:48 PM

#

true

subtle lake Sep 28, 2024, 10:20 PM

#

f(19,19) = 8909115018130190380110405132161117908

#

now i sleep

teal tide Sep 28, 2024, 10:23 PM

#

now you sleep

twilit seal Sep 29, 2024, 8:28 AM

#

rapid ravine elaborate

i think the closest i can get to what i mean is that im somewhere else

rapid ravine Sep 29, 2024, 10:19 AM

#

twilit seal i think the closest i can get to what i mean is that im somewhere else

hmmmm

#

so like

#

head in the clouds?

#

like if someone stares at you you're not actually looking back cause you're distracted?

twilit seal Sep 29, 2024, 10:21 AM

#

no not like that

#

idk how to say

rapid ravine Sep 29, 2024, 10:21 AM

#

smh

#

u gotta explain yourself woman

subtle lake Sep 29, 2024, 11:18 AM

#

f(20,20) = 75332748233894465141809677114505805331037

vivid pulsar Sep 29, 2024, 12:13 PM

#

What

subtle lake Sep 29, 2024, 12:14 PM

#

just posting some numbers that go past the oeis page for f(n,n)

twilit seal Sep 29, 2024, 12:26 PM

#

how long do these take to compute

subtle lake Sep 29, 2024, 12:27 PM

#

😬

#

left it running overnight

twilit seal Sep 29, 2024, 12:38 PM

#

owie

eternal thistle Sep 29, 2024, 2:45 PM

#

Goated

tough kettle Oct 1, 2024, 11:58 AM

#

subtle lake 😬

14.9s system

#

just run it as a direct process to make it much faster

subtle lake Oct 1, 2024, 11:59 AM

#

what does that mean

tough kettle Oct 2, 2024, 1:16 AM

#

lol

tough kettle Oct 2, 2024, 1:16 AM

#

subtle lake what does that mean

run it using cpython not jupyter

#

actually run it with dandidapython

twilit seal Oct 2, 2024, 8:13 AM

#

jupyter uses cpython

tough kettle Oct 2, 2024, 12:07 PM

#

yeah but its slow

#

you can see by the cpu times

tough kettle Oct 11, 2024, 10:08 PM

#

x

azure compass Oct 11, 2024, 10:31 PM

#

@tough kettle hi!!!!
is it ok if i participate here????

tough kettle Oct 11, 2024, 10:31 PM

#

yeah

azure compass Oct 11, 2024, 10:32 PM

#

thanks!!!!

#

also what are the 14 solutions for 3x3? i only got 12

tough kettle Oct 11, 2024, 10:34 PM

#

i call them solutions

azure compass Oct 11, 2024, 10:34 PM

#

tough kettle i call them solutions

oh ok

tough kettle Oct 13, 2024, 2:36 PM

#

keepalive

vivid pulsar Oct 14, 2024, 4:09 AM

#

keepalive?

#

also is anyone here doing usamts

violet pond Oct 14, 2024, 3:22 PM

#

vivid pulsar also is anyone here doing usamts

yep

#

im writing up my solutions rn 😄

tough kettle Oct 14, 2024, 3:24 PM

#

vivid pulsar keepalive?

so the thread doesn't close

vivid pulsar Oct 14, 2024, 4:55 PM

#

violet pond im writing up my solutions rn 😄

same

#

i did like half my prob 5 at 3-4 am today so not it looks so jumpleb😭

violet pond Oct 14, 2024, 4:56 PM

#

lol ye

vivid pulsar Oct 14, 2024, 4:56 PM

#

im doing prob 4 last omg its so hard to explain

violet pond Oct 14, 2024, 5:04 PM

#

vivid pulsar im doing prob 4 last omg its so hard to explain

no discus

vivid pulsar Oct 14, 2024, 5:26 PM

#

ok

vivid pulsar Oct 14, 2024, 6:51 PM

#

https://tenor.com/view/donald-duck-ducktales-ducktales2017-the-spear-of-selene-ithaquack-gif-21612838

Tenor

#I forget how we found this problem