# Generate an infinite group of infinite galaxies [closed]

Here is the challenge as proposed by @trichoplax thanks to him for consolidating my post and standarizing it to PPCG common-rules.

• A galaxy is a group of numbers where each one is mapped to another via a precise function f either a symbolic one or mathematical, a structure of numbers sharing some common points with this challenge i got inspired from with an exception that a galaxy sequence is not cyclic, but holds in a black hole, where more than one number can be mapped to it.
• A black hole is a specific unique number from a galaxy where all numbers (not individually) are mapped transitively to it, by repeating a function f infinitely over an infinite far number in a same galaxy, or just once if a number is the closest in the same galaxy, for example if the function is the ceiling of the square root then a black hole for the biggest galaxy so far excluding only the number 1 is 2, because mapping the closest number 3 or the infinite repetitively leads to the same number.

Conceive a universe of an infinite number of distinct galaxies where all galaxies encompass an infinite number of integers.

Note that the example of ceiling of square root is banned for two reasons:

• The galaxy {1} is finite.
• There is a finite number of galaxies.

A valid example, is dividing by the smallest prime factor. This gives an infinite number of infinite galaxies.

2*2*3*5*5*7, 2*3*5*5*7, 3*5*5*7, 5*5*7, 5*7, 7, 7*5*5*5, 7*5*5*5....
5*5*7*11, 5*7*11, 11*7*7*7... , ....
...


Or one galaxy as a tree:

2*2*5 - 2*5 \
\
2*3*5 - 3*5 - 5
3*3*5 /       |
/
2*5*5 - 5*5 /
3*5*5 /


Each galaxy consists of all numbers that share the same largest prime factor, and the function takes them all step by step towards the black hole which is that prime factor.

Note also, you may choose any domain of integers as long as the range is infinite, i mean you can exclude a range of numbers that makes the rest still boundless like {1,0} from last example.

Your program takes any integer input via a function's dimension , STDIN, and outputs an integer as the image mapped from this preimage, otherwise prints "error" or any string prespecified for an outputless range of enteries.

For the same example:

(IN/OUTPUT)

   20
10

15
5

77
11

0
'undefined'

1
'undefined'


This is so shortest program in bytes wins.

I would have really liked to add a bonus-score for anyone who succeeds to find a function generating a universe without trees, alas, bonuses for code-golf are excluded.

• Do they have to have common points? Commented May 27, 2016 at 11:08
• To clarify: a "black hole" is a fixed point of the function f (a number n such that f(n) = n), and a "galaxy" is the set of all numbers that eventually reach the same black hole when f is applied to them repeatedly, correct? And the challenge is to implement a function f that has an infinite number of infinitely large galaxies? Can f have finite cycles or finite galaxies in addition to these infinite galaxies? Commented May 27, 2016 at 12:27
• Also, you might want to add that in your example, every prime is a black hole (so the function is actually "divide by smallest prime factor, unless input is prime; in that case do nothing"). This has caused some confusion. Commented May 27, 2016 at 12:47
• That six-line sentence in the second item is... not the easiest I've read :-) Commented May 27, 2016 at 16:04
• I still don't understand what this is asking, and based on discussion in answer comments, I'm not the only one. Can someone please state the requirement in standard mathematical terminology?
– xnor
Commented Jun 1, 2016 at 19:46

# Python 2, 15 bytes

lambda n:n>>n%2


The domain is nonnegative integers.

• You ninja'd me :( I was just discussing this in chat...
– orlp
Commented May 27, 2016 at 13:11
• @orlp If I'm understanding the question correctly, 0, 1, 3, 7, ... is a galaxy. Commented May 27, 2016 at 13:15
• Does 2 form an infinite galaxy? Commented May 27, 2016 at 13:19
• @LeakyNun Yep. 2, 5, 11, 23, etc. Commented May 27, 2016 at 13:20
• @feersum I confused it with a different solution, never mind :)
– orlp
Commented May 27, 2016 at 13:21

# Python, 40 bytes

lambda n:n&~-n and int(bin(n)[3:],2)or n


Clear the top bit if there's more than one bit set, otherwise returns the number itself. The domain is the positive integers.

First couple numbers (in binary):

    1:     1
10:    10
11:     1
100:   100
101:     1
110:    10
111:    11
1000:  1000
1001:     1
1010:    10
1011:    11
1100:   100
1101:   101
1110:   110
1111:   111
10000: 10000
10001:     1
10010:    10
10011:    11
10100:   100
10101:   101
10110:   110
10111:   111
11000:  1000
11001:  1001
11010:  1010
11011:  1011
11100:  1100
11101:  1101
11110:  1110
11111:  1111

• this is nice one ! Commented May 27, 2016 at 13:06

# Pyth, 2 bytes

hP


Domain: integers ≥ 2. Function: smallest prime factor. Black holes: primes.

(This seems too simple but seems to satisfy the challenge as far as I can tell. Is the challenge missing some requirement? For example, perhaps the function is supposed to be surjective?)

• " all members must be mapped to a blackhole transitively or directly" hmmm that does not satisfy the "transitively" condition. but I will take it as valid solution. Commented May 28, 2016 at 23:11
• @Agawa001 The condition that you wrote is satisfied—“all numbers are A or B” does not require “some numbers are A”. But I think this solution is not interesting, so if you fix the challenge requirements to exclude it, I am happy to delete it. I would suggest that you add a requirement that the function is surjective. (That would imply the existence of arbitrarily long transitive chains to any black hole.) Commented May 28, 2016 at 23:16
• the function is already surjective, but it can be bijective where there is no trees, i dont know how u relate things Commented May 28, 2016 at 23:20
• @Agawa001 No it isn’t. Surjectivity is when the image is the entire codomain: that is, for every y, there is at least one x with f(x) = y. en.wikipedia.org/wiki/Surjective_function Commented May 29, 2016 at 0:11
• @Agawa001 Your requirement is an “or”, so I get to choose which side of the “or” to satisfy. If I choose “directly” every time, I have satisfied the requirement. If that is not what you intended, you should change the requirement. (Besides, “directly” is a special case of “transitively” anyway. Also, my name is not andres.) Commented May 29, 2016 at 8:25

# Pyth, 5 4 bytes, no trees

I am working under the assumption that the author intended for the function to be surjective, and for “no trees” to mean that only black holes have multiple preimages. (Technically, a tree with only one branch is still a tree.)

ahxt


Domain: positive integers. Function: f(x) = |((x − 1) XOR x) + 1 − x|. Black holes: powers of 2. Galaxies:

1 ← 3 ← 5 ← 7 ← 9 ← 11 ← ⋯,
2 ← 6 ← 10 ← 14 ← 18 ← 22 ← ⋯,
4 ← 12 ← 20 ← 28 ← 36 ← 44 ← ⋯,
8 ← 24 ← 40 ← 56 ← 72 ← 88 ← ⋯,

• please you can knock away that assumption u deduced by urself that a domain is surjective, the only condition for my puzzle, that numbers are either bridged to a "spleen" or "blackhole" or "terminus" by other peers, or just it is drawn directly to this point, maybe i made a slip here, so i should rather use "and" ? Commented May 29, 2016 at 10:57
• @Agawa001 This solution is valid whether or not the function is required to be surjective. However, if it is not, then my non-surjective 2-byte solution is also valid and also has no trees, which would make this 5-byte solution kind of pointless. (It is apparent that you have some complaint about my 2-byte solution, but I still cannot figure out what that complaint is. Let’s keep that conversation over there.) Commented May 29, 2016 at 11:25
• i cant understand your solution, it does subtract the rearmost runs of 0's followed by '1' shifted by 1 from x, does it have another translation ? Commented May 29, 2016 at 11:45
• is this a universe with tree-less infinite galaxies ? even for bh's ? if so i would accept that unique answer. Commented May 29, 2016 at 11:46
• @Agawa001 You are going to have to explain what you mean by “tree-less”. What is a “tree”? Formally, a tree is any graph where there is a unique path from the root to each node. That is not the case in any graph with a self-loop (such as a black hole). If you exclude the self-loops, then every galaxy in every valid solution is a tree. I am doing my best to try to infer what you meant to say, but that is clearly not working, and this would be much clearer to me and to everyone else if you could give a formal definition. Commented May 29, 2016 at 11:56

# Python 2, 29 bytes

lambda n:int("0"+n[1:])or n


Strips off the first digit, unless that makes the number 0. The domain is the positive integers.

## 05AB1E, 9 bytes

Code:

Dpiëf¬¹s/


Explanation:

Dpi         # if input is prime return input
ë        # else
f¬      # get the smallest primefactor
¹s/   # divide input by this factor


Domain:{n | n∈N ∧ n>1}

Range: {n | n∈N ∧ n>0}

• please, provide the range of surjective (domain,codomain) and the function used (even if it is already embedded in the question core) Commented May 27, 2016 at 10:57
• @Agawa001: Something like this? Commented May 27, 2016 at 11:11
• I guess you might have to update your code. Commented May 27, 2016 at 12:44
• @LeakyNun: Thanks for the heads up Commented May 27, 2016 at 13:11

## JavaScript (ES6), 12 bytes

n=>n%2?n:n/2


The domain is the positive integers. The black holes are the odd numbers.

• n=>n/(2-n%2) has the same byte count Commented May 27, 2016 at 13:21

# Pyth, 5 bytes

|stzz


Port of my Python answer (the decimal version).

## matlab (156)

a=input('');if find(num2str(a)=='0')a,return,end,b=char(num2str(a)-1);c=str2num(b);if find(b=='0')if(find(num2str(c)=='0')&c)c,else 10^nnz(b)+c,end,else c,end

• I declare my self the winner of that imaginary score because i am the first who finds a universe of galaxies without trees.

• Domain is decimal numbers with two or more significant digits. and not a difference bteween two arbitray digits squals to 9 .

• Black holes are numbers which have significant zeros, either in the extreme bottom, or between two strictly positive digits 12300131 , 123400 , 10 , ....

• The function is decrementing all decimal digits of that number by 1, if we stumble upon a significant zero we declare a blackhole, if non-significant zero at the head of this number, precede it with 1 then the result topped by unsignificant zeos.

• There is no trees in that galaxy except the blackhole which absorbs an infinite tree-less streams of finite numbers.

• I don’t understand how this fits your requirements. 11 maps to 0, which is not in your domain. And the galaxies are not infinite; for example, the galaxy 98 → 87 → 76 → 65 → 54 → 43 → 32 → 21 → 10 has no other members. Commented May 28, 2016 at 23:35
• @downvoter fixed Commented May 29, 2016 at 8:01
• @AndersKaseorg they do have infinite other members , 232 → 121 → 10 , 2232 → 1121 → 10 , 22222232 → 11111121 → 10 ..... Commented May 29, 2016 at 8:04
• @AndersKaseorg and for ur remark it is fixed, i replaced 9 by 1, now : 22 → 11 → 100 / 322 → 211 → 100 / ..... Commented May 29, 2016 at 8:07
• Your change added other preimages of 10, but now the galaxy 90 has no other members. Commented May 29, 2016 at 8:49