The Nineteenth Byte

AviFS

00:10

@Adám Oh, it seems like a pretty big con to me to have such similar names.

"Array Cast" and "APL Cast"

It could easily be confusing. And it also just starts to sounds pretty dry, imo.

Ginger

00:29

@mathcat Don't worry, it's going to be a Klein Stein (a Klein bottle shaped like a stein)

@mousetail get this: it doesn't work yet

@user They're icon-theme-dependant

I have an icon browser program I use to choose them

OldSandboxPosts

01:00

Sandbox posts last active a week ago: KotH: Build an Organism

AviFS

03:09

@Adám Stripping leading zeroes makes sense because f(42) = f(042). That rule alone takes care of the property that f(0) = 1. Why do you strip trailing zeroes, though?

I'm presuming it's so that exponents are ignored, and scientific notation is uncomplicated, but I could still see it just being equal to zero whenever there's a trailing zero.

Either f(0.00123) = f(12300) = 6
Or f(0.00123) = f(12300) = 0

I feel like I'd have to have even the slightest sense of its application, in order to figure out which more useful, haha

AviFS

By the way, what are the zeroes in .00123 called? Are those still called leading zeroes, or do they have a special name?

@AviFS Ooh, you could encode both pieces of information by making it negative if there are one or more non-leading zeroes, hehe

So f(123) = f(1.23) = f(0.123) = f(0.1230) = f(0123) = 6
But f(1230) = f(.0123) = -6

Whether or not there's a 0 in the number is arguably more useful information than whether the sign of the number is negative. It's already easy to get the sign of the number in any coding lang, but whether the number contains a 0 would actually be unique info.

AviFS

03:51

@Simd Including, or not including, empty subsets?

@Simd @user I don't believe your guys' jump to a constant of (3/4) works, unless I'm missing some assumptions.

Is this given that |A| < |B|?

Bubbler

04:09

A ⊆ B implies A can be equal to B

AviFS

@Bubbler True true, I meant |A| <= |B|.

Bubbler

and do you mean "|A| <= |B| is an assumption"?

Btw, I think (3/4)^n is correct. In order to satisfy A ⊆ B, every element e in {1..n} must be one of three cases (out of four equally probable events):
- e is in A, e is in B
- e is in A, e is not in B <- this must be avoided
- e is not in A, e is in B
- e is not in A, e is not in B

AviFS

@Bubbler I understood the reasoning, but it doesn't seem to work out when I test it by hand.

Bubbler

How do you choose A and B?

They must be randomly chosen out of 2^n possible subsets of {1..n}

AviFS

The summing over all possible values, feels a little "expected value-y" to me. I'm wondering if I'm missing out on some tricks because I never did expected values. On the one hand, I can imagine it being the case that it would work, but I can also imagine it being the case that it doesn't work.

Bubbler

04:22

I don't do sum

user is incorrect

AviFS

Aren't you kinda summing over all possible sizes of A and B, and then dividing by |A|*|B|?

Not here, but in principle.

Bubbler

No, size is irrelevant.

AviFS

@Bubbler Oh wait, right you never use size here.

That does make sense now that you've totally abstracted away A & B.

Wait no, no it doesn't. Because you're still assuming that all four of those scenarios are equally likely.

You are making that assumption, right?

Bubbler

@AviFS It is not an assumption.

When you choose a subset of A uniformly at random, for every number e in {1..n}, the probability of e being in A is 1/2.

AviFS

Hmm, that's the step I don't follow. That's the part that seems like an average-y thing.

@Bubbler Right, that's been my hangup.

Alright, I can see it.

It's like a change in perspective. From thinking about picking an element of A, to thinking about an e being picked.

Which of course is a boolean, and is just as likely to be picked as not picked.

Bubbler

04:30

Yes.

hyper-neutrino

the intuitive way to see that is that if you list out the powerset of a set, then there are an equal number with e as without, which you can see by just excluding e, and then if you add e back in, you have the existing powerset and then a copy of each set containing e

AviFS

@Bubbler Thank you.

@Bubbler Does all of this follow from similar logic, though?

Oh right, it does. It becomes 1/2 * 1/2. I gotcha!!

Bubbler

Yes, from independence of events.

AviFS

Wow. Very elegant.

@hyper-neutrino Ooh, that's really nice.

Have you seen the Numberphile video on powersets as the corners of a hypercube?

hyper-neutrino

I don't think I have but that does seem to be a very logical representation

AviFS

04:33

@hyper-neutrino This reminds me of that. When you add e back in, to each copy of the existing sets of the powerset, that's the equivalent of extruding the hypercube into another dimension.

hyper-neutrino

ah, yes that makes a lot of sense

AviFS

I can explain after, but I have a question about the problem before.

@hyper-neutrino I'm shook. I watched a half hour video to understand that whole analogy, haha

@Bubbler Can you check my case for N=2?

hyper-neutrino

well, I'd need to watch the video to fully understand the video, I'm just saying the analogy you drew makes sense to me :P there might be details I'd need more time to get

AviFS

This is part of what threw me off the (3/4)^n. But it involved listing out all possible sizes of A & B. I'm curious where I went wrong.

Bubbler

I think you need to take into account the number of cases for each choice of "size of A & B"

AviFS

04:39

I divided that by 9 and I got 11/18.

Bubbler

so your table should go more like

0 0:  1 x1
0 1:  1 x2
0 2:  1 x1
1 0:  0 x2
1 1:  .5 x4
1 2:  1 x2
2 0:  0 x1
2 1:  0 x2
2 2:  1 x1

and divide the sum by 16.

AviFS

Oh shoot.

Damn, that'll do it, haha

Thank you.

Let's check what I get now!

Radvylf Programs

Thank you Amazon for curbstomping my power supply box...luckily the side that got crushed was just cables instead of the PSU lol

AviFS

1+2+1+2+2+1 = 9

Yup! 9/16. Thanks a bunch, Bubbler.

Bubbler

Np :)

AviFS

04:41

That's pretty cool.

I wanna see someone do this with combinatorial sums, though. I have so many summation manipulations scribbled down, haha

And there's a whole chapter (like 20-30 something pages) in Graham, Knuth, Patashnik's Concrete Mathematics just on summation identities of N choose K, and derivations + examples.

Bubbler

For each possible size b of B (which covers nCb possibilities of B), there are 2^b possible subsets of B. Sum(nCb * 2^b) happens to be an expansion of (2+1)^n, which is 3^n.

AviFS

@hyper-neutrino No, that's about it.

The fact that powersets could be represented as the corners of a hypercube was a novel insight for me. And that was really most of the video.

But yeah, once you have that, you generate the n+1-hypercube by copying the existing hypercube over, and just adding the new element to each copied set. So:

0 dimensions (point):
ø

1 dimension (line):
ø --- A

2 dimensions (square):
ø ---- A
|      |
|      |
B --- AB

hyper-neutrino

yeah, that makes sense. that representation format seems familiar like I've seen it somewhere before... it is a novel idea though, I don't think I've thought of powersets that way before either

it also gives you a nice property that an edge exists if and only if the sets differ by exactly one missing/extra element or in the context of bitmaps, the xor is a power of two

AviFS

So, powersets of {}, {A} and {A, B}.

And you can imagine that for the powerset of {A, B, C}, you can take the square and "pull" it up into three dimensions, with the Cs on that dimension. In other words, make another square copying the exact same elements, and just add a C to each corner. Then just connect each corner.

By doing exactly that, he then drew a 4d-hypercube of the elements of the powerset of {A,B,C,D} which was pretty fun.

Brady had to skip some of the drawing :p

@hyper-neutrino Yup, you're way ahead of me!

But yeah, someone in the comments was talking about how this had applications in error-correcting codes, and some other linear-algebra/cryptography stuff, which I can totally imagine because of those nice properties.

@hyper-neutrino Plus, you even know precisely which element they differ by. On the x axis, you're adding/removing A. On the y axis, you're adding/removing B. On the z axis, you're adding/removing C... Each element has its own unique axis.

Equivalently, each element has its own unique dimension, which kinda sounds cooler ; )

Should we bookmark things like this? haha

hyper-neutrino

04:57

hm, yeah that is pretty interesting. i'm sure there are a lot of applications for which it could be quite powerful; for me though it just seems like a cool idea because I am nowhere near knowledgeable enough to put stuff like this into use :P

AviFS

@hyper-neutrino 'Course, haha. But it's a useful intuition to have for any number of math problems, or coding challenges. Like the one that just came up ; )

Adám

06:23

@AviFS How are "Array" and "APL" similar to each other? Because they both begin with "A" and (if "APL" is pronounced "apple") have two syllables?

Simd

07:31

Hello!

Sandbox Posts

11:14

0

A: Sandbox for Proposed Challenges

Resolve a string containing \b, \t and \r code-golf Meta: better title There are many characters that do something special when printed in a terminal. Way to many to list. In this case, we'll consider 2 specifically: \r, or \x0d is a cartridge return. This will move the cursor back to the start ...

Sandbox Posts

12:41

0

A: Sandbox for Proposed Challenges

Flipping between languages code-golf I find it fun to write a program in a language A, that outputs a program in language B, that outputs back in A, and so on. Your task is similar to this, described below: Challenge: Select two languages A and B (note: swapping will change the nature of your an...

UndoneStudios

@SandboxPosts whoa, that was fast

Simd

12:59

What is the golfiest code to print 4.56458314100509023986577469558 in C?

lyxal

that's numberwang!

on to round 2, someone to play.

Simd

@lyxal what is numberwang??

lyxal

That Mitchell and Webb Look - Numberwang

►

also youtube.com/watch?v=ZH-cXBhkl-E

it's like Mornington Crescent but numbers

Simd

:)

A great cultural reference!

But I still want to know the answer :)

UndoneStudios

I should know, but at the same time, I don't

lyxal

13:08

@Simd think a British panel game show but satire and a sketch from a larger comedy show

@Simd I heard about it from a letter from a Mrs Trellis of North Wales

UndoneStudios

4.56458314100509023986577469558 gets trimmed in Python, dunno if it gets trimmed in C as well

For a start: main(){puts("4.56458314100509023986577469558");}

mousetail

@Simd What's the significance of that specific value?

@UndoneStudios ato.pxeger.com/… Take ABC=python 3.9, 3.10, and 3.11

Adám

That's R(10), no?

Simd

14:08

@mousetail it's the first value from my challenge

@Adám yes

@lyxal total class :)

@UndoneStudios can you try with float128?

@UndoneStudios I think you will need

#include <quadmath.h>
#include <stdio.h>

int main(void) {
__float128 value = 4.56458314100509023986577469558Q;

The printf function has a special format specifier for float128 values, which is %Qf I think

But I haven't got a C compiler here

It would be great if someone could try it out please

mousetail

Doesn't seem to work with a long double either: ato.pxeger.com/…

Simd

I wouldn't expect long double to work

But I think you left out stdio?

mousetail

It's optional

Golfers usually omit it

Long double is 128 bit though right?

Simd

@mousetail I believe not

mousetail

ato.pxeger.com/…

Sizeof seems to say it's 16 bytes

Simd

14:19

On the x86 architecture, most C compilers implement long double as the 80-bit extended precision type supported by x86 hardware

It's 80 bits on a standard Linux box at least

"generally stored as 12 or 16 bytes to maintain data structure alignment"

mousetail

It's 16 bytes on my generic linux machine too

Simd

@mousetail right but sadly not 128 bit for the purpose of precision

Unless you are doing something clever with gcc

mousetail

Oh that's sad

But maybe you can use your __float128 on ATO still?

Simd

@mousetail try this

#include <float.h>

printf("%e %e %Le\n", FLT_EPSILON, DBL_EPSILON, LDBL_EPSILON);

What does it give you?

mousetail

You can do that on ATO

Simd

14:34

I am on my phone which makes everything difficult

mousetail

ato.pxeger.com/…

Simd

Thanks

So 10^(-19) is about 2^(-63)

It's 80 bits

Simd

19:00

If you toss n biased coins, what's the probability of getting at least one tail and one head?

Seggan

1/2?

Simd

CMQ ^^

Seggan

at least or exactly one head?

Simd

@Seggan at least

And one tail

You need both to happen

Seggan

argh i just took probability why cant i solve this

Simd

19:04

:)

Seggan

probably 1 - P(no heads) + P(no tails)

Simd

If there are no heads they are all tails of course

The answer for n=3 is 3/4

Seggan

@Simd how does that change it?

Simd

Do you get 3/4 for n=3?

If the coins are fair I mean

Just to test

Yes you do

:)

Seggan

yep

i think its 1 - 2 / (2^n)

since the chance for all heads/tails is 1 / (2^n)

the chance for either of them is 2 / (2^n)

then subtract that from 1 to get the chances of that not happening

Simd

19:38

@Seggan thanks!

is anyone able to code in a fast language? (I can't really)

Seggan

choose one: rust or kotlin

(i cant program today tho)

Simd

@Seggan rust another day?

maybe tomorrow?

user

@Simd I can write Hello World in C :P

Simd

@user awesome!

Hola mundo too?

thanks to chatgpt I can too :)

user

Oh yeah

I can say Hello World in any language

Simd

19:45

:)

user

This is what they call being a polyglot right?

Simd

brainfuck?

Seggan

@Simd tomorrow might work

user

Well, there are brainfuck generators out there, so I guess so

Simd

@Seggan cool

Seggan

19:46

what u want me to write?

oops

had my russian keyboard on :P

Simd

@Seggan I want to count how many integers less than 2^30 have no factors below 2^14

Seggan

may i ask why?

user

yesterday, by Simd

CMC count the number of composite numbers less than 2^30 with no factors less than 2^14

sus

Seggan

@Simd 0

user

Other than 1, I assume

Surely there are primes greater than 2^14 and less than 2^30

Possibly even a handful of composite numbers that are products of such primes

mathcat

20:03

Is 16 the only number which can be written as a**b and b**a where a =/ b and a, b E N?

smh wolfram alpha isn't returning anything

Simd

20:21

@Seggan why 0?!

@user quite a lot :)

Seggan

@Simd all numbers have 1 as a factor :P

Simd

@Seggan ah yes.. :) no factors above 1 and less than 2^14

@user yes!

@user suspect?

@Seggan I am hoping it is something like 57676950 but I would love an exact answer

@Seggan please tell me how wrong I am :)

Seggan

tmrw

Simd

thanks!

I look forward to being humiliated ;)

mathcat

20:38

Hey guis

heard of the game no thanks?

The rules are fairly simple, and I think it'd make a rather good koth

There's no clear strategy either

what do you think?

user

21:06

@Simd Wait really? I thought for a composite number to meet those criteria, it'd have to be the product of two primes between 2^14 and 2^15

@Simd It often seems like your CMCs are something you actually need in the real world, not just fun little questions you thought of in the moment. Which is fine, but if it's a real problem you're facing and you need a solution in a particular language meeting some particular criteria, you might as well include that in your CMC

@mathcat Looks like it'd make for an interesting KotH. I've never made a KotH though so don't actually listen to me

Ginger

22:25

How would I go about finding the most popular tags on a SE site? Asking for a friend, who isn't me :p

Unrelated String

codegolf.stackexchange.com/tags

the default order is by popularity :P

Ginger

bruh

Bubbler

22:48

yesterday, by Radvylf Programs

It's 6492559

Newly Featured Posts

23:18

9

Q: Shortest disk image that boots UEFI

Presumably everybody here knows that for the legacy BIOS, the tiniest bootable disk image is 512 bytes (the lower bound is due to the 2-byte magic at offset 510), and there is a bootsector demoscene where people try to fit the entire demo into the 510 bytes of usable space. Now that the BIOS is b...

code-golf

Neil

@cairdcoinheringaahing seems that the chain was longer than I thought: codegolf.stackexchange.com/a/256052

caird coinheringaahing

Crossed out 44 is still 44 :(

lyxal

@Bubbler that's numberwang!

Time to go to the math board

New Posts

23:41

0

Q: Find the Prime Signature

The Prime Signature of a number is the list of the exponents of the prime factors of a number, sorted in descending order (exponents of 0 are ignored). Inspired by Combo Class's "The Magnificent Patterns of Prime Signatures" video. For example, the prime factorization of 6860 is 2 * 2 * 5 * 7 * 7...

code-golf number-theory primes factoring

Transcript for